Description

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.

Input Format

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

The second line contains $n$ integers $a_i$.

Output Format

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

4 3
3 4 5 5

9

4 3
4 4 3 3

7

Hint

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$.