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
#include <bits/stdc++.h>
using namespace std;
int main() 
{
	int n,m,i;
	long long sum = 0;
	scanf("%d %d",&n,&m);
	priority_queue<int> q;
	for(i=0;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		q.push(x);
	}
	while (m--)
	{
		int x = q.top();
		q.pop();
		q.push(x / 2);
	}
	while (!q.empty())
	{
		sum += q.top();
		q.pop();
	}
	cout << sum;
	return 0;
}
