当前没有测试数据。

题目描述

小 T 是一个旅行爱好者，他决定在这个小镇上度过一个长达 N 天的假期。这个小镇以其迷人的火车旅行路线而闻名，游客们可以欣赏到壮观的风景。

小 T 对这个小镇的火车旅行充满期待，他会在接下来 N 天每天坐一趟火车旅行，但他也希望能够以最优惠的方式享受这段旅程。

火车公司提供了两种票价选项：每天按照当日的价格支付车费，或者购买一日票套餐。

火车公司提供的一日票套餐价格为 P 元，里面包含了 D 张一日票。不论这趟火车当日的车费是多少钱，每张一日票都可以支付一趟火车的费用。一日票​必须以套餐的形式购买​，也就是说如果小 T 想购买一日票，可以花费 P 元购买 1 个套餐。当然，购买多个套餐也是可以的。

如果小 T 购买套餐中的一日票，在 N 天之后有剩余，剩余的票不能退款，他会把这些剩余的票保存起来，下次假期来小镇旅行时再使用。

小 T 想要找到一种购票方案，使得他的旅行总费用最低。

现在，小 T 需要您的帮助来计算出他进行 N 天旅行的​最小可能总费用​，让他能够以最划算的方式畅享这段火车旅程。

输入

第一行输入旅游天数 N，每个套餐包含一日票的张数 D，每个一日票套餐价格 P。

第二行输入 N 个数，第 i 个整数代表第 i 天正常车费 $F_i$。

输出

进行 N 天旅行的最小可能总费用。

样例

输入复制

5 2 10
7 1 6 3 6

输出复制

20

输入复制

3 1 10
1 2 3

输出复制

6

输入复制

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出复制

3000000000

说明

【样例 1 解释】

以下是最优惠的购票方案之一：

小 T 会购买 1 个套餐，套餐中有 2 张票，售价 10 元，他会把这两张票用于第 1 天和第 3 天的火车旅行，第 2 天、第 4 天和第 5 天，他会按照当日的火车票价支付车费。

按这个方案，他需要支付的总费用为 10+1+3+6=20。

【样例 2 解释】

最优惠的方案为：每天都按照当天的票价支付，总金额为 1+2+3=6 。

【样例 3 解释】

最优惠的方案为：购买三个套餐得到 9 张一日票，在 8 天的旅行中，每天使用一张一日票。假期结束，小 T 会剩余 1 张票。

请注意，答案可能超过32位整数类型。

【数据范围】

对于 30% 的数据： 1≤N≤2×1$0^2$,1≤D≤2×1$0^2$,1≤P≤1$0^3$,1≤$F_i$​≤1$0^3$。

对于 60%60% 的数据： 1≤N≤2×1$0^3$,1≤D≤2×1$0^3$,1≤P≤1$0^6$,1≤$F_i$​≤1$0^6$

对于 100% 的数据： 1≤N≤2×1$0^5$,1≤D≤2×1$0^5$,1≤P≤1$0^9$,1≤$F_i$​≤1$0^9$