题目描述

$N$ 个物品，买第 $i$ 个要 $A_i$ 元。现有 $M$ 个抵扣券，使用 $Y$ 个抵扣券可以使需要 $A_i$ 的物品只需要付 $\left\lfloor\frac{A_i}{2^Y}\right\rfloor$ 元。求出购买所有物品需要的最少金钱。

输入格式

第一行两个整数 $N, M$。

第二行 $N$ 个整数 $A_i$，表示每个物品的价格。

$1 \le N, M \le 10^5$，$1 \le A_i \le 10^9$。

输出格式

购买所有物品需要的最少金钱。

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