题目描述

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?

高桥打算逐一购买 $N$ 件商品。

他购买的 $i$ 件商品的价格是 $A_i$ 日元（日本货币）。

他有 $M$ 张折扣券，在购买商品时可以使用任意数量的折扣券。

如果在购买价格为 $X$ 日元的商品时使用了 $Y$ 张优惠券，那么他可以用 $\frac{X}{2^Y}$ 的价格买到该商品。(四舍五入到最接近的整数）日元。

购买所有商品最少需要多少钱？

输入格式

输入内容按以下格式标准输入：

$N$ $M$
$A_1$ $A_2$ $...$ $A_N$

输出格式

打印购买所有物品所需的最低金额。

样例 #1

样例输入 #1

3 3
2 13 8

样例输出 #1

9

样例 #2

样例输入 #2

4 4
1 9 3 5

样例输出 #2

6

样例 #3

样例输入 #3

1 100000
1000000000

样例输出 #3

0

样例 #4

样例输入 #4

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

样例输出 #4

9500000000

说明

数据规模与约定

• 所有输入值均为整数。
• $1 \leq N, M \leq 10^5$
• $1 \leq A_i \leq 10^9$

样例 $1$ 解释

我们可以用 $9$ 日元购买所有物品，如下所示：

• 用 $2$ 日元购买 $1$ （st）号商品，不含门票。
• 用 $2$ 张门票，花 $3$ 日元购买 $2$ 件nd商品。
• 用 $1$ 张门票，花 $4$ 日元购买 $3$ 件商品。

样例 $3$ 解释

我们可以用 $100000$ 张门票以 $0$ 日元购买价格为 $1000000000$ 日元的商品。