Busy Beaver đang tham gia kỳ thi đầu tiên tại Viện Công nghệ Kiểm tra Cường độ Cao (MITIT). Kỳ thi rất dài và thời gian có hạn, vì vậy cậu ấy cần lập một chiến lược làm bài.

Kỳ thi kéo dài $M$ phút với $N$ bài toán. Bài toán thứ $i$ có độ khó là một số nguyên dương $d_i$. Một bài toán có độ khó $d$ sẽ tốn $d$ phút để giải và mang lại $d+1$ điểm. Không có điểm thành phần cho việc chỉ giải một phần bài toán.

Ngoài ra, nếu Busy Beaver nộp bài trước khi hết giờ $X$ phút ($0 \le X \le M$), cậu ấy sẽ nhận được $X$ điểm thưởng cộng vào tổng điểm của mình.

Số điểm tối đa mà Busy Beaver có thể đạt được là bao nhiêu?

Dữ liệu vào

Mỗi bộ dữ liệu chứa nhiều trường hợp kiểm thử. Dòng đầu tiên chứa số lượng trường hợp kiểm thử $T$ ($1 \le T \le 10^4$). Tiếp theo là mô tả của các trường hợp kiểm thử.

Dòng đầu tiên của mỗi trường hợp kiểm thử chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $1 \le M \le 10^9$).

Dòng thứ hai của mỗi trường hợp kiểm thử chứa $N$ số nguyên cách nhau bởi dấu cách $d_1, \dots, d_N$ ($1 \le d_i \le 10^9$).

Đảm bảo rằng tổng $N$ trên tất cả các trường hợp kiểm thử không vượt quá $10^5$.

Dữ liệu ra

Với mỗi trường hợp kiểm thử, in ra một số nguyên duy nhất: số điểm tối đa có thể đạt được.

Nhiệm vụ con

• ($15$ điểm) Có đủ thời gian để hoàn thành tất cả các bài toán.
• ($15$ điểm) Tất cả các bài toán đều có cùng độ khó.
• ($70$ điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

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

Kết quả 1

10
49
10
12

Ghi chú

Trong trường hợp kiểm thử đầu tiên, Busy Beaver có thể giải các bài toán có độ khó $1, 2$ và $4$ trong $7$ phút. Busy Beaver sẽ nhận được $2 + 3 + 5 = 10$ điểm theo cách này (không có điểm thưởng vì không còn thời gian dư).

Trong trường hợp kiểm thử thứ hai, Busy Beaver có thể giải tất cả bốn bài toán và dư ra $5$ phút, nhận được tổng cộng $49$ điểm: $16 + 11 + 6 + 11 = 44$ điểm từ các bài toán, cộng với $5$ điểm thưởng.

Trong trường hợp kiểm thử thứ ba, Busy Beaver không thể giải bất kỳ bài toán nào trong thời gian cho phép! Vì vậy, cách tốt nhất là nộp bài trống ngay sau khi bắt đầu, điều này mang lại $10$ điểm thưởng.

Trong trường hợp kiểm thử thứ tư, Busy Beaver có thể giải hai bài toán có độ khó $4$ và $5$ trong $9$ phút; Busy Beaver sẽ nhận được $1$ điểm thưởng vì còn dư $1$ phút, và đạt tổng cộng $5 + 6 + 1 = 12$ điểm.