p02912 AtCoder Beginner Contest 141 - Powerful Discount Tickets
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?

Constraints

* All values in input are integers.
* 1 \leq N, M \leq 10^5
* 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N M
A_1 A_2 ... A_N


Output

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

Examples

Input

3 3
2 13 8


Output

9


Input

4 4
1 9 3 5


Output

6


Input

1 100000
1000000000


Output

0


Input

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000


Output

9500000000
```python
n,m = map(int,input().split())
a = [-int(i) for i in input().split()]
import heapq
heapq.heapify(a)
for i in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a,-(-x//2))

print(-sum(a))
```