题目描述

Takahashi要逐个购买$N$件商品。

第$i$件商品的价格是$A_i$日元(日本的货币)

他有$M$张折扣券，他可以在购买商品时使用任意张。

如果购买价格为$X$日元的商品时使用了$Y$张券，那么他可以以 $ \frac{X}{2^Y}(向下取整)的价格购买商品。

购买所有商品所需的最少金额是多少?

输入

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

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

输出

打印出购买所有商品所需的最少金额。

3 3
2 13 8

9

样例解释

我们可以以9日元的价格购买所有商品，方法如下：

以2日元购买第一件商品，没有使用折扣券，

以3日元的价格用2张券购买第二件商品。

以4日元的价格用1张券购买第三件商品

4 4
1 9 3 5

6

1 100000
1000000000

样例解释

我们可以用100000张券以0日元的价格购买价值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$