题目描述

小爱需要将 $n$ 件商品全部买回家，其中第 $i$ 件商品的价格为 $a_i$。

小爱有 $m$ 张对折券，对每件商品，可以使用任意多张对折券，效果是叠加的。若一件商品原价是 $A$，对该商品使用 $k$ 张对折券后，则该商品的价格将变成 $\lfloor\frac{A}{2^k}\rfloor$。其中 $\lfloor\rfloor$是向下取整的意思。

请计算应该如何分配这些对折券才能使得打折后的商品总价之和变得最小。

输入格式

• 第一行：两个整数表示 $n$ 与 $m$
• 第二行：$n$ 个整数 $a_1,a_2,\dots, a_n$ 表示各个商品的原价

输出格式

• 单个整数表示答案

3 2
50 100 300

225

样例解释 1

全部同在300上

数据范围

• $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$