该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc141_d [ABC141D] Powerful Discount Tickets

题目描述

高桥君计划依次购买 $N$ 件商品，每次购买一件。

第 $i$ 件商品的价格为 $A_i$ 日元。

高桥君手中有 $M$ 张优惠券。

在购买商品时，可以任意选择使用任意数量的优惠券。

如果在购买价格为 $X$ 日元的商品时使用了 $Y$ 张优惠券，则该商品可以以 $\left\lfloor \frac{X}{2^Y} \right\rfloor$ 日元（向下取整）购买。

请问，至少需要多少钱才能买下所有商品？

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出买下所有商品所需的最小金额。

样例 1

输入

3 3
2 13 8

输出

9

样例 2

输入

4 4
1 9 3 5

输出

6

样例 3

输入

1 100000
1000000000

输出

0

样例 4

输入

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$

样例解释 1

如果按照如下方式使用优惠券，总共只需 $9$ 日元即可买下所有商品。

• 第 $1$ 件商品不使用优惠券，以 $2$ 日元购买。
• 第 $2$ 件商品使用 $2$ 张优惠券，以 $3$ 日元购买。
• 第 $3$ 件商品使用 $1$ 张优惠券，以 $4$ 日元购买。

样例解释 3

如果在购买价格为 $1000000000$ 日元的商品时使用 $100000$ 张优惠券，则可以以 $0$ 日元购买该商品。

由 ChatGPT 4.1 翻译