Maximum Subset Sum Under Target

You are given an integer x (the target sum) and an array A of n positive integers. Your task is to select a subset of elements from A such that the sum of the selected elements is as large as possible without exceeding x.

This problem can be solved using dynamic programming techniques similar to the 0/1 knapsack problem. In particular, define a DP array where:

\(dp[j] = \max(dp[j], dp[j - a] + a)\) for each element \(a\) in the array, iterating backwards from \(x\) to \(a\).

Your goal is to compute, for each test case, the maximum subset sum that does not exceed x.

inputFormat

The input is read from the standard input (stdin). The first line contains an integer T denoting the number of test cases. Each test case consists of two lines:

• The first line contains two integers n and x, where n is the number of elements in the array and x is the target sum.
• The second line contains n space-separated integers representing the elements of array A.

outputFormat

For each test case, output a single line containing the maximum possible sum of any subset of elements from A that does not exceed x.

## sample

3
5 10
1 2 3 4 5
3 7
2 2 6
4 100
20 30 50 70

10
6
100

</p>