取饼干 - 代码源竞赛平台

题目描述

盘子里有 $k$ 块饼干，现有 $n$ 位客人，每位客人依次取一次饼干。第 $i$ 位客人希望取走 $a_i$ 块饼干，但每次取走的数量不能超过盘中剩余饼干数量的一半。

具体地，若一位客人取饼干前盘中还剩 $r$ 块饼干，那么第 $i$ 位客人实际取走的数量为

$$\min\left(a_i,\left\lfloor\frac{r}{2}\right\rfloor\right)$$

其中，$\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。客人取走饼干后，盘中剩余的饼干数量随之减少。

你可以任意安排这 $n$ 位客人取饼干的顺序。请问所有客人取完后，最多一共能取走多少块饼干？

输入格式

第一行包含两个整数 $n,k$，分别表示客人数和盘子里最初的饼干数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 位客人希望取走的饼干数量。

输出格式

输出一个整数，表示所有客人最多能够取走的饼干总数。

样例

2 10
1 10

6

4 9
2 2 2 2

7

样例解释

对于样例 $1$，可以先让第 $2$ 位客人取饼干，他取走 $\min(10,\lfloor 10/2\rfloor)=5$ 块，盘中剩余 $5$ 块。随后第 $1$ 位客人取走 $\min(1,\lfloor 5/2\rfloor)=1$ 块，两人共取走 $6$ 块。若交换两人的顺序，则只能共取走 $5$ 块，因此答案为 $6$。

对于样例 $2$，所有客人的需求相同，无论怎样安排顺序，四位客人依次取走的饼干数量都是 $2,2,2,1$，共取走 $7$ 块。

数据规模

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le k\le 2\times 10^{14}$，$1\le a_i\le 10^9$。