Score : 400 points
Takahashi is going to buy N items one by one.
The price of the i-th item he buys is A_i yen (the currency of Japan).
He has M discount tickets, and he can use any number of them when buying an item.
If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.
What is the minimum amount of money required to buy all the items?
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N
Print the minimum amount of money required to buy all the items.
3 3 2 13 8
9
We can buy all the items for 9 yen, as follows:
4 4 1 9 3 5
6
1 100000 1000000000
0
We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.
10 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
9500000000