分数: 400 点
问题陈述
高桥要买 N 项目一一列出。
的价格 i- 他购买的第件物品是 A_i 日元(日本的货币)。
他有 M 折扣券,购买商品时可以使用任意数量的折扣券。
If Y 门票用于购买已定价的商品 X 日元,他可以获得该物品 \frac{X}{2^Y} (四舍五入到最接近的整数)日元。
购买所有物品所需的最低金额是多少?
约束
- 输入中的所有值都是整数。
- 1 \leq N, M \leq 10^5
- 1 \leq A_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 ... A_N
输出
打印购买所有物品所需的最低金额。
示例输入 1
3 3 2 13 8
示例输出 1
9
我们可以购买所有物品 9 日元,如下:
- 购买 1-st 项目 2 日元不含门票。
- 购买 2-nd 项目 3 日元与 2 门票。
- 购买 3-rd 项目 4 日元与 1 票。
示例输入 2
4 4 1 9 3 5
示例输出 2
6
示例输入 3
1 100000 1000000000
示例输出 3
0
我们可以购买该商品的价格 1000000000 日元 0 日元与 100000 门票。
示例输入 4
10 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 4
9500000000