题目描述

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

5 2 10
7 1 6 3 6

20

提示

【样例解释】

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

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

按这个方案，他需要支付的总费用为 10 + 1 + 3 + 6 = 20。 请注意，答案可能超过32位整数类型。

【数据范围】

对于 100%的数据：1≤N≤2×10^5,1≤D≤2×10^5,1≤P≤10^9,1≤Fi​≤10^9。