Discount Coupons

Input

The first line contains two integers $N$ and $M$ (1 \leq N, M \leq 10^5). The second line contains $N$ integers A_1, A_2, \dots, A_N (1 \leq A_i \leq 10^9).

Output

Print the minimum amount of money required to buy all the items.

Examples

Note

• In the first example, all items can be purchased for $10$ manats as follows: Buy the first item for $3$ manats without using any discount coupons. The second item can be bought using $2$ discount coupons for

  \left\lfloor \frac{15}{2^2} \right\rfloor = 3

  manats. The third item can be bought using $1$ discount coupon for $4$ manats. The total amount spent is 3 + 3 + 4 = 10 manats.

• In the second example, by using $1000$ discount coupons, you can buy an item originally costing $1000000$ manats for $0$ manats.

Scoring

This problem consists of $5$ subtasks as described below: