题目名称

对折券

题目描述

小爱有 $n$ 件商品需要购买，第 $i$ 件商品的价格为 $a_i$ 。小爱拥有 $m$ 张对折券，对于每件商品，可使用任意多张对折券，且效果可叠加。若一件商品原价为 $A$ ，使用 $k$ 张对折券后，该商品价格变为 $\lfloor\frac{A}{2^k}\rfloor$（$\lfloor\ \rfloor$ 为向下取整）。需计算如何分配这些对折券，能使打折后商品总价最小。

输入格式

• 第一行：两个整数 $n$ 与 $m$ ，分别表示商品数量和对折券数量。
• 第二行：$n$ 个整数 $a_1,a_2,\cdots,a_n$ ，表示各商品的原价。

输出格式

输出一个整数，表示打折后商品的最小总价。

数据范围

• 对于 30% 的数据：$1 \leq n \leq 10$，$1 \leq m \leq 10$ 。
• 对于 60% 的数据：$1 \leq n \leq 500$，$1 \leq m \leq 500$ 。
• 对于 100% 的数据：$1 \leq n \leq 200,000$，$1 \leq m \leq 200,000$ ，$1 \leq a_i \leq 1,000,000,000$ 。

样例

输入

3 2
50 100 300

输出

225

说明：将 2 张对折券都用在 300 元的商品上。