Maximum Subsequence Sum Without Exceeding Target

Given an array of positive integers and a target sum \(M\), your task is to determine the maximum sum obtainable by selecting a subset of the array such that the total sum does not exceed \(M\). In other words, if the array is \(A\) with \(N\) elements, find a subset \(S \subseteq \{0,1,...,N-1\}\) that maximizes \(\sum_{i \in S} A[i]\) while satisfying \(\sum_{i \in S} A[i] \le M\). If no valid non-empty subset exists, the answer is 0.

inputFormat

The input starts with an integer \(T\) denoting the number of test cases. Each test case consists of two lines:

• The first line contains two space-separated integers \(N\) and \(M\), representing the number of elements and the target sum respectively.
• The second line contains \(N\) space-separated positive integers, representing the array elements.

outputFormat

For each test case, output a single integer on a new line: the maximum subsequence sum that does not exceed \(M\).

2
5 9
1 2 3 4 5
4 8
8 3 5 7

9
8