(knapsack1.*)

Cho số nguyên dương \(s\) và dãy số \(A\) gồm \(n\) số nguyên dương \(a_{1},a_{2},\ldots,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 \leq t \leq 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},\ldots,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	Output
2 3 12 1 6 9 5 9 3 4 4 4 8	12 9