Cho số nguyên dương ~ s ~ và dãy số ~ A ~ gồm ~ n ~ số nguyên dương ~ a_1, a_2, …, a_n ~. Hãy chọn một số phần tử trong dãy số ~ A ~ sao cho tổng các phần tử được chọn là lớn nhất nhưng không vượt quá ~ s ~. Lưu ý mỗi số trong dãy ~ A ~ có thể được chọn 0 hoặc 1 hoặc nhiều lần.

Yêu cầu: Hãy cho biết tổng lớn nhất chọn được.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ t ~ ~ ( 1 ≤ t ≤ 10 ) ~ cho biết số lượng testcase.

• ~ t ~ nhóm dòng tiếp theo mỗi nhóm dòng cho biết thông tin về 1 testcase:

  • Dòng đầu ghi 2 số nguyên dương ~ n, s ~.
  • Dòng tiếp theo ghi ~ n ~ số nguyên dương ~ a_1, a_2, …, a_n ~.

Tất cả các số được cho không vượt quá ~ 2000 ~.

Kết quả

Đưa ra ~ t ~ số, mỗi số trên một dòng là kết quả tương ứng với testcase trong input

Ví dụ:

Input 1

2
3 12
1 6 9
5 9 
3 4 4 4 8 

Output 1

12
9