Maximum Subsequence Sum

You are given an array of integers and two numbers n and m. The integer n represents the number of elements in the array and m is an upper bound. Your task is to select a subsequence (i.e. a subset in any order) from the array such that the sum of its elements is as large as possible but does not exceed m.

This problem can be formulated as the following optimization:

Find a subset S of the array such that \[ \text{max}\Big\{\sum_{x\in S} x \;:\;\sum_{x\in S} x \le m\Big\} \]

You need to answer multiple test cases, where each test case is given in the input.

inputFormat

The input begins with an integer T (T \(\ge\) 1) on the first line representing the number of test cases. Each test case consists of two lines:

• The first line contains two integers n and m separated by a space.
• The second line contains n space-separated integers, representing the elements of the array.

outputFormat

For each test case, output the maximum subsequence sum (which is less than or equal to m) on a new line.

## sample

3
5 10
2 4 6 8 10
3 15
1 5 7
4 7
3 1 4 2

10
13
7

</p>