题目描述
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
输入格式
见题面
输出格式
见题面