小 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
以下是最优惠的购票方案之一：
小 T 会购买 1 个套餐，套餐中有 2 张票，售价 10 元，他会把这两张票用于第 1 天和第 3 天的火车旅行，第 2 天、第 4 天和第 5 天，他会按照当日的火车票价支付车费。
按这个方案，他需要支付的总费用为 10 + 1 + 3 + 6 = 20。
最优惠的方案为：每天都按照当天的票价支付，总金额为 1+2+3=6 。
最优惠的方案为：购买三个套餐得到 9 张一日票，在 8 天的旅行中，每天使用一张一日票。假期结束，小 T 会剩余 1 张票。
请注意，答案可能超过32位整数类型。
对于 30 \% 的数据： 1 \le N \le 2 \times 10^2 , 1 \le D \le 2 \times 10^2 , 1 \le P \le 10^3 , 1 \le F_i \le 10^3 。
对于 60 \% 的数据： 1 \le N \le 2 \times 10^3 , 1 \le D \le 2 \times 10^3 , 1 \le P \le 10^6 , 1 \le F_i \le 10^6 。
对于 100 \% 的数据： 1 \le N \le 2 \times 10^5 , 1 \le D \le 2 \times 10^5 , 1 \le P \le 10^9 , 1 \le F_i \le 10^9 。