题目描述

商店里有 $N$ 件商品，第 $i$ 件物品价格 $A_i$ 元。

有 $K$ 张优惠券，一个优惠券可以用于一个物品上，同一个物品可以使用若干张优惠券（可能不使用优惠券）。

一张优惠券可以降低价格 $X$ 元，在 $a$ 元的物品上使用 $k$ 张优惠券后的价格降低为 $\max{a - kX, 0 }$ 元。

请求出买下所有物品的最少价格。

输入格式

第一行输入三个整数 $N$ $K$ $X$

接下来一行输入 $A_1$ $A_2$ $\ldots$ $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\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ K,\ X\ \leq\ 10^9$
• $1\ \leq\ A_i\ \leq\ 10^9$

样例 1 解释

在第 $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$ 日元，这是可能的最低价格。