题目描述

$N$ 個の商品があります。$i\ =\ 1,\ 2,\ \ldots,\ N$ について、$i$ 番目の商品の値段は $A_i$ 円です。

高橋君は $K$ 枚のクーポンを持っています。
$1$ 枚のクーポンは $1$ つの商品に対して使用することができ、$1$ つの商品に対してはクーポンを何枚でも（ $0$ 枚でもよい）使用することができます。 値段が $a$ 円の商品に対して $k$ 枚のクーポンを使用すると、その商品を $\max\lbrace\ a\ -\ kX,\ 0\rbrace$ 円で買うことができます。

高橋君がすべての商品を買うために支払う合計金額の最小値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $X$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

答えを出力せよ。

题目大意

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

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

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

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

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$
• 入力はすべて整数

Sample Explanation 1

$1$ 番目の商品に対してクーポン $1$ 枚、$3$ 番目の商品に対してクーポン $1$ 枚、$5$ 番目の商品に対してクーポン $2$ 枚を使用すると、 - $1$ 番目の商品を $\max\lbrace\ A_1-X,\ 0\ \rbrace\ =\ 1$ 円で買うことができ、 - $2$ 番目の商品を $\max\lbrace\ A_2,\ 0\ \rbrace\ =\ 3$ 円で買うことができ、 - $3$ 番目の商品を $\max\lbrace\ A_3-X,\ 0\ \rbrace\ =\ 3$ 円で買うことができ、 - $4$ 番目の商品を $\max\lbrace\ A_4,\ 0\ \rbrace\ =\ 5$ 円で買うことができ、 - $5$ 番目の商品を $\max\lbrace\ A_5-2X,\ 0\ \rbrace\ =\ 0$ 円で買うことができます。 よって、すべての商品を $1\ +\ 3\ +\ 3\ +\ 5\ +\ 0\ =\ 12$ 円で買うことができ、これが最小です。