参加考试 - 题目

Busy Beaver 正在参加 Maximally Intensive Testing Institute of Technology (MITIT) 的第一场考试。考试时间很长，但时间有限，因此他需要制定一个策略。

考试时长为 $M$ 分钟，共有 $N$ 道题目。第 $i$ 道题目的难度值为正整数 $d_i$。完成一道难度为 $d$ 的题目需要 $d$ 分钟，得分为 $d+1$ 分。完成题目的一部分没有分数。

此外，如果 Busy Beaver 在考试结束前 $X$ 分钟交卷（$0 \le X \le M$），他将获得 $X$ 分的额外奖励分。

请问 Busy Beaver 能得到的最高总分是多少？

每个测试点包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 10^4$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $N$ 和 $M$ ($1 \le N \le 10^5$, $1 \le M \le 10^9$)。

每个测试用例的第二行包含 $N$ 个空格分隔的整数 $d_1, \dots, d_N$ ($1 \le d_i \le 10^9$)。

保证所有测试用例的 $N$ 之和不超过 $10^5$。

对于每个测试用例，输出一个整数：最高可能得分。

4
4 7
1 2 3 4
4 45
15 10 5 10
5 10
20 30 40 50 60
5 10
8 4 13 5 7

在第一个测试用例中，Busy Beaver 可以用 $7$ 分钟完成难度为 $1$、$2$ 和 $4$ 的题目。这样 Busy Beaver 将得到 $2 + 3 + 5 = 10$ 分（没有奖励分，因为没有剩余时间）。

在第二个测试用例中，Busy Beaver 可以完成所有四道题目并剩余 $5$ 分钟，总得分为 $49$ 分：题目得分 $16 + 11 + 6 + 11 = 44$ 分，加上 $5$ 分奖励分。

在第三个测试用例中，Busy Beaver 无法在规定时间内完成任何一道题目！因此最好的做法是在计时开始后立即交卷，这样可以获得 $10$ 分奖励分。

在第四个测试用例中，Busy Beaver 可以用 $9$ 分钟完成难度为 $4$ 和 $5$ 的两道题目；由于剩余 $1$ 分钟，Busy Beaver 将获得 $1$ 分奖励分，总得分为 $5 + 6 + 1 = 12$ 分。

QOJ.ac