题目描述

高桥打算逐个购买 $N$ 件物品。

他购买的第 $i$ 件物品的价格是 $A_i$ 日元（日本的货币）。

他有 $M$ 张折扣券，购买物品时可以使用任意数量的折扣券。

如果购买售价为 $X$ 日元的物品时使用了 $Y$ 张折扣券，那么他可以以 $\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 日元购买所有物品：

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

示例输入2

4 4
1 9 3 5

示例输出2

6

示例输入3

1 100000
1000000000

示例输出3

0

我们可以以 0 日元的价格使用 10000 张折扣券购买标价为 1000000000 日元的物品。

示例输入4

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

示例输出4

9500000000