C - Coupon 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

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

高橋君は K 枚のクーポンを持っています。
1 枚のクーポンは 1 つの商品に対して使用することができ、1 つの商品に対してはクーポンを何枚でも（ 0 枚でもよい）使用することができます。 値段が 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

出力

答えを出力せよ。

入力例 1

5 4 7
8 3 10 5 13

出力例 1

12

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 円で買うことができ、これが最小です。

入力例 2

5 100 7
8 3 10 5 13

出力例 2

0

入力例 3

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

出力例 3

112

Score : 300 points

Problem Statement

There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).

Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.

Print the minimum amount of money Takahashi needs to buy all the items.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K, X \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K X
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

5 4 7
8 3 10 5 13

Sample Output 1

12

By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:

  • buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
  • buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
  • buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
  • buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
  • buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,

for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.

Sample Input 2

5 100 7
8 3 10 5 13

Sample Output 2

0

Sample Input 3

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

Sample Output 3

112