优惠券

题目描述

商店里有 $N$ 件商品。对每个 $i = 1, 2, \ldots, N$,第 $i$ 件商品的价格为 $A_i$ 日元(日本货币)。

Takahashi 有 $K$ 张优惠券。

每张优惠券可用于一件商品。同一件商品可以使用任意数量的优惠券,也可以一张都不用。对价格 $a$ 日元的商品使用 $k$ 张优惠券时,可以以 $\max\lbrace a - kX, 0\rbrace$ 日元的价格购买它。

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

输入格式

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

N K X
A_1 A_2 … A_N

输出格式

输出答案。

样例

5 4 7
8 3 10 5 13

12

在第 1 件商品上用 1 张优惠券、第 3 件商品上用 1 张优惠券、第 5 件商品上用 2 张优惠券时,Takahashi 可以:

以 $\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

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le K, X \le 10^9$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数。