P12413 「YLLOI-R1-T2」Christmas Star


Little Y needs to buy $n$ items in a store, and the price of the $i$-th item is $a_i$ yuan. Before buying these items, Little Y can buy as many coupons as he wants. Each coupon costs $w$ yuan. Each coupon gives a $1$ yuan discount on any item, but any item can be discounted to a minimum of $0$ yuan. (Coupons are not considered items) After paying for each item, Little Y will also receive one more coupon. Now Little Y wants to know the minimum amount of money needed to buy all the items. Note: All coupons are permanent.

The first line contains two integers $n$ and $w$. The second line contains $n$ integers $a_i$.

Output a single integer — the minimum amount of money Little Y needs to spend to buy all the items.

### Explanation **Sample 1:** Here is an optimal solution. First, purchase $3$ discount coupons, costing $3 \times 3 = 9$ yuan. Then, use $0$ yuan to buy the first product ($3$ discount coupons reduced the price by $3$ yuan), and receive one more coupon. Next, use $0$ yuan to buy the second product ($4$ discount coupons reduced the price by $4$ yuan), and receive one more coupon. Next, use $0$ yuan to buy the third product ($5$ discount coupons reduced the price by $5$ yuan), and receive one more coupon. Finally, use $0$ yuan to buy the fourth product ($6$ discount coupons reduced the price by $5$ yuan, because the minimum discount for any product is $0$ yuan), and receive one more coupon. Therefore, the total cost is $9 + 0 + 0 + 0 + 0 = 9$ yuan. **Sample 2:** Here is an optimal solution. First, purchase $1$ discount coupon, costing $1 \times 3 = 3$ yuan. Then, use $2$ yuan to buy the fourth product ($1$ discount coupon reduced the price by $1$ yuan), and receive one more coupon. Next, use $1$ yuan to buy the third product ($2$ discount coupons reduced the price by $2$ yuan), and receive one more coupon. Next, use $1$ yuan to buy the second product ($3$ discount coupons reduced the price by $3$ yuan), and receive one more coupon. Finally, use $0$ yuan to buy the first product ($4$ discount coupons reduced the price by $4$ yuan), and receive one more coupon. Therefore, the total cost is $3 + 2 + 1 + 1 + 0 = 7$ yuan. ### Constraints **This problem uses subtask scoring.** - Subtask 1 (10 pts): $\forall a_i = i$. - Subtask 2 (10 pts): $w = 1$. - Subtask 3 (20 pts): $n, a_i, w \leq 10$. - Subtask 4 (30 pts): $n, a_i, w \leq 1000$. - Subtask 5 (30 pts): No additional constraints. For all data: - $1 \leq n \leq 10^5$. - $1 \leq a_i, w \leq 10^9$.