← 返回题目列表

AtCoder · abc141_d

D. 强力优惠门票

中文机器翻译题面 查看原题

分数: 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