折扣券

题目描述

高桥君计划按顺序一个一个购买 $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

如下使用折扣券，可以合计 $9$ 日元购买所有商品：

• 第 $1$ 个购买的商品不使用折扣券，用 $2$ 日元购买。
• 第 $2$ 个购买的商品使用 $2$ 张折扣券，用 $3$ 日元购买。
• 第 $3$ 个购买的商品使用 $1$ 张折扣券，用 $4$ 日元购买。

4 4
1 9 3 5

6

1 100000
1000000000

0

购买 $1000000000$ 日元的商品时使用 $100000$ 张折扣券，可以 $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$