题目描述

小高在一家商店里有$N$件商品。对于每个$i=1,2,...,N$，第$i$件商品的价格是$A_i$元。小高有$K$张优惠券。每张优惠券可以用于一件商品。你可以在同一件商品上使用任意数量的优惠券，包括零张。在一件价格为$a$元的商品上使用$k$张优惠券，可以以$\max\{a - kX, 0\}$元的价格购买它。请计算小高购买所有商品所需的最小金额。

输入格式

输入从标准输入中以下列格式给出：

$N$ $K$ $X$

$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出所求答案。

样例

5 4 7
8 3 10 5 13

12

5 100 7
8 3 10 5 13

0

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

112

样例1解释

通过在第1件商品上使用1张优惠券，第3件商品上使用1张优惠券，以及第5件商品上使用2张优惠券，小高可以：

• 以 $\max{A_1-X, 0} = 1$ 元购买第1件商品，
• 以 $\max{A_2, 0} = 3$ 元购买第2件商品，
• 以 $\max{A_3-X, 0} = 3$ 元购买第3件商品，
• 以 $\max{A_4, 0} = 5$ 元购买第4件商品，
• 以 $\max{A_5-2X, 0} = 0$ 元购买第5件商品，

总计花费 $1 + 3 + 3 + 5 + 0 = 12$ 元，这是可能的最小金额。

数据范围

• $1 ≤ N ≤ 2 × 10^5$
• $1 ≤ K, X ≤ 10^9$
• $1 ≤ A_i ≤ 10^9$
• 所有输入值都是整数。

来源

• AtCoder ABC246C