Powerful Discount Tickets

题目描述

Takahashi 将要一个接一个地购买 $N$ 件物品。 他购买的第 $i$ 件物品的价格是 $A_i$ 日元（日本的货币）。 他有 $M$ 张折扣券，购买物品时可以使用任意数量的折扣券。 如果在购买价格为 $X$ 日元的物品时使用了 $Y$ 张券，则该物品的价格可以变为 $\frac{X}{2^Y}$（向下取整到最接近的整数）日元。 购买所有物品所需的最少金额是多少？

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出购买所有物品所需的最少金额。

3 3
2 13 8

9

4 4
1 9 3 5

6

1 100000
1000000000

0

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

9500000000

提示

输入中的所有值都是整数。 $1 \leq N, M \leq 10^5$ $1 \leq A_i \leq 10^9$我们可以用 $9$ 日元买到所有物品，方法如下：

第 1 件物品不使用券以 $2$ 日元购买。 第 2 件物品使用 $2$ 张券以 $3$ 日元购买。 第 3 件物品使用 $1$ 张券以 $4$ 日元购买。
我们可以用 $100000$ 张券把标价为 $1000000000$ 日元的物品买到 $0$ 日元。

标签: AtCoder|abc141D

来源

AtCoder|abc141D