시험 치기 - Problema

Busy Beaver는 MITIT(Maximally Intensive Testing Institute of Technology)에서 첫 시험을 치르고 있습니다. 시험은 길고 시간은 제한되어 있어, 그는 전략을 세워야 합니다.

시험 시간은 $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는 난이도가 $1, 2, 4$인 문제들을 $7$분 만에 풀 수 있습니다. 이 경우 Busy Beaver는 $2 + 3 + 5 = 10$점을 얻습니다 (남은 시간이 없으므로 보너스 점수는 없습니다).

두 번째 테스트 케이스에서, Busy Beaver는 네 문제를 모두 풀고 $5$분의 여유 시간을 가질 수 있으며, 총 $49$점을 얻습니다: 문제 점수 $16 + 11 + 6 + 11 = 44$점에 보너스 점수 $5$점이 더해집니다.

세 번째 테스트 케이스에서, Busy Beaver는 주어진 시간 내에 어떤 문제도 풀 수 없습니다! 따라서 가장 좋은 방법은 시험 시작 직후에 빈 시험지를 제출하여 $10$점의 보너스 점수를 받는 것입니다.

네 번째 테스트 케이스에서, Busy Beaver는 난이도가 $4$와 $5$인 두 문제를 $9$분 만에 풀 수 있습니다. $1$분의 여유 시간이 남으므로 $1$점의 보너스 점수를 받아 총 $5 + 6 + 1 = 12$점을 얻습니다.

QOJ.ac