Minimizing Total Cost with Discount Coupons

In this problem, there are n items that need to be purchased with prices a_i (in yuan) for i from 1 to n. Before buying any item, you can buy as many discount coupons as you like. Each coupon costs w yuan. Every coupon can discount the price of any item by \(1\) yuan; however, the discount on any single item cannot reduce its price below \(0\) yuan. (Coupons are not counted as items.)

Moreover, after paying for each item, you are awarded one additional coupon (free of charge). All coupons are permanent and can be used at any time (but note that a coupon can only be applied once to reduce a price by \(1\) yuan).

Your task is to determine the minimum total amount of money required to purchase all n items. You are allowed to choose the order in which you buy the items and to purchase coupons either before starting any purchase or during the process. When buying an item, you may use any coupons that you currently have. However, if you need additional coupons (i.e. you do not have enough free coupons to cover your desired discount on that item), you must purchase the extra coupons at the cost of \(w\) yuan each.

Coupon usage rule when buying an item:

• If you have at least \(a_i\) coupons before buying the i-th item, you can use \(a_i\) coupons so that you pay \(0\) for that item. Afterwards, you lose \(a_i\) coupons but gain 1 coupon, so your coupon count decreases by \(a_i - 1\).
• If you have fewer than \(a_i\) coupons (say, \(p\) coupons with \(p < a_i\)), you have two options:
  • On‐demand purchase: Use your free \(p\) coupons and pay the remaining \(a_i - p\) yuan for the item.
  • Pre‐purchase strategy: Alternatively, you may have already purchased enough extra coupons beforehand so that you have at least \(a_i\) coupons before buying this item. In that case, you pay nothing for the item and your coupon count becomes \(p - a_i + 1\).

Note that when \(w < 1\), buying extra coupons is cheaper than paying full price for the undiscounted part; when \(w \ge 1\) the cost of a coupon is at least as expensive as not using one. Therefore, the optimal strategy is to choose the best between:

1. Processing the items in increasing order (so that you might not need to spend extra money if you have enough free coupons) and purchase extra coupons on‐demand if needed. In this strategy, if you start with 0 coupons, then for the first item (if its price is positive) you must purchase enough coupons to cover its full price, and for each subsequent item you use your free coupon (gained from the previous purchase) if possible, otherwise you purchase the missing coupons. The total extra cost in this on‐demand strategy is \(c \cdot \bigl(a_1 - 0\bigr) + \sum_{i=2}^{n} c \cdot \max(a_i - 1, 0)\), where \(c = 1\) if \(w \ge 1\) and \(c = w\) if \(w < 1\).
2. A pre‐purchase strategy where you buy an initial number of coupons \(k\) (at a total cost of \(k \cdot w\)) so that you can buy every item with full coupon discounts (i.e. using coupon discounts fully on every item). If the items (when sorted in increasing order) have prices \(a_1, a_2, \dots, a_n\), then in order to never need extra purchases, the initial coupons must satisfy the condition \[ k \ge a_1,\quad k - a_1 + 1 \ge a_2,\quad k - (a_1+a_2) + 2 \ge a_3,\quad \dots,\quad k - \sum_{i=1}^{n-1}a_i + (n-1) \ge a_n. \] In other words, the minimum required \(k\) is \[ k = \max_{1 \le j \le n} \Bigl(\sum_{i=1}^{j}a_i - (j-1)\Bigr). \] The total cost for this strategy is \(k\cdot w\).

Your goal is to output the minimum total cost among these two strategies.

inputFormat

The first line contains two integers \(n\) and \(w\) \((1 \le n \le 10^5,\ 0 \le w \le 10^9)\) — the number of items and the cost of each coupon in yuan.

The second line contains \(n\) non-negative integers \(a_1, a_2, \dots, a_n\) \((0 \le a_i \le 10^9)\), where \(a_i\) is the price of the \(i\)-th item (in yuan).

outputFormat

Output a single integer: the minimum total amount of money (in yuan) required to purchase all items.

sample

2 2
5 1

5