D - 强大的折扣券

得分：400分

问题描述

Takahashi要逐个购买N件商品。

第i件商品的价格是Ai日元（日本的货币）。

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

如果购买价格为X日元的商品时使用了Y张券，那么他可以以$\frac{X}{2^Y}$（向下取整）的价格购买商品。

购买所有商品所需的最少金额是多少？

约束

• 输入的所有值均为整数。
• 1 ≤ N, M ≤ $10^5$
• 1 ≤ Ai ≤ $10^9$

输入

输入以以下格式从标准输入给出：

N M

A1 A2 ... AN

输出

打印出购买所有商品所需的最少金额。

3 3
2 13 8

9

我们可以以9日元的价格购买所有商品，方法如下：

• 以2日元购买第一件商品，没有使用折扣券。
• 以3日元的价格用2张券购买第二件商品。
• 以4日元的价格用1张券购买第三件商品。

4 4
1 9 3 5

6

1 100000
1000000000

0

我们可以用100000张券以0日元的价格购买价值1000000000日元的商品。

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

9500000000