102462: [AtCoder]ABC246 C - Coupon
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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
Input
题意翻译
商店里有 $N$ 件商品，第 $i$ 件物品价格 $A_i$ 元。 有 $K$ 张优惠券，一个优惠券可以用于一个物品上，同一个物品可以使用若干张优惠券（可能不使用优惠券）。 一张优惠券可以降低价格 $X$ 元，在 $a$ 元的物品上使用 $k$ 张优惠券后的价格降低为 $\max{a - kX, 0 }$ 元。 请求出买下所有物品的最少价格。Output
得分：300分
部分
问题描述
商店里有N件商品。对于每个$i = 1, 2, \ldots, N$，第i件商品的价格是$A_i$日元（日本的货币单位）。
Takahashi有K张优惠券。
每张优惠券可以用于一件商品。同一件商品可以使用任意数量的优惠券，包括零张。在一件价格为$a$日元的商品上使用$k$张优惠券可以让你以$\max\lbrace a - kX, 0\rbrace$日元的价格购买它。
输出Takahashi购买所有商品所需的最低金额。
部分
约束
* $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
```
Takahashi可以通过在第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$日元，这是最低可能的价格。
部分
样例输入 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
```