23492번 - Subset Sum 다국어

문제

Chiaki has $n$ integers $a_1, a_2, \dots, a_n$ and another integer $c,ドル and she would like to choose a subset of the $n$ integers whose sum does not exceed $c$. Find the maximum possible sum of the chosen subset.

입력

There are multiple test cases. The first line of the input contains an integer $T$ (1ドル \le T \le 2 \times 10^4$), indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $c$ (1ドル \le n \leq 2 \times 10^4,ドル 1ドル \leq c \leq 10^9$). The second line contains $n$ integers $a_1, a_2, \dots, a_n$ (1ドル \leq a_i \leq 2 \times 10^4$).

The sum of all $n$ does not exceed 2ドル \times 10^4$.

출력

For each test case, output an integer denoting the answer.

제한

힌트