当前没有测试数据。

C - 优惠券

得分：300分

问题描述

商店里有$N$个商品。其中第$i$个商品的价格为$A_i$日元（日本的货币单位）。

高橋有$K$张优惠券。
每张优惠券可以在一件商品上使用。你可以使用任意数量的优惠券，可能是零，但是只能在同一件商品上使用。在价格为$a$日元的商品上使用$k$张优惠券可以以$\max\lbrace a - kX, 0\rbrace$日元的价格购买它。

输出高橋购买所有商品所需的最少金额。

约束

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

输入

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

$N$ $K$ $X$

$A_1$ $A_2$ $\ldots$ $A_N$

输出

输出答案。

5 4 7
8 3 10 5 13

12

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

• 用$\max\lbrace A_1-X, 0 \rbrace = 1$日元购买第1个商品，
• 用$\max\lbrace A_2, 0 \rbrace = 3$日元购买第2个商品，
• 用$\max\lbrace A_3-X, 0 \rbrace = 3$日元购买第3个商品，
• 用$\max\lbrace A_4, 0 \rbrace = 5$日元购买第4个商品，
• 用$\max\lbrace A_5-2X, 0 \rbrace = 0$日元购买第5个商品，

总计花费$1 + 3 + 3 + 5 + 0 = 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