試験を受ける - 問題

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$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、2つの整数 $N, M$ ($1 \le N \le 10^5, 1 \le M \le 10^9$) が含まれます。

各テストケースの2行目には、$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 は難易度 $1, 2, 4$ の問題を $7$ 分で解くことができます。この場合、Busy Beaver は $2 + 3 + 5 = 10$ 点を獲得します（残り時間がないため、ボーナスポイントはありません）。

2番目のテストケースでは、Busy Beaver は4問すべてを解いても $5$ 分の余裕があり、合計 $49$ 点を獲得できます。内訳は、問題から $16 + 11 + 6 + 11 = 44$ 点、ボーナスポイントが $5$ 点です。

3番目のテストケースでは、Busy Beaver はどの問題も制限時間内に解くことができません。そのため、最善の策は試験開始直後に白紙で提出することであり、これにより $10$ 点のボーナスポイントが得られます。

4番目のテストケースでは、Busy Beaver は難易度 $4$ と $5$ の2問を $9$ 分で解くことができます。$1$ 分の余裕があるため $1$ 点のボーナスポイントが加算され、合計 $5 + 6 + 1 = 12$ 点を獲得します。

QOJ.ac