參加考試 - Problem

Busy Beaver 正在參加他在麻省理工學院（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