Taco's Health Optimization

You are given a series of fruits, each with a health value. Your task is to find the maximum sum of a contiguous subsequence of fruits whose total does not exceed a given target value \(T\).

Formally, given an integer \(N\) representing the number of fruits and a sequence \(a_1, a_2, \dots, a_N\) representing the health values, find the maximum value of \(\sum_{i=l}^{r}a_i\) for some \(1 \leq l \leq r \leq N\) such that:

\[ \sum_{i=l}^{r}a_i \leq T \]

If no contiguous subarray satisfies the condition, output 0.

The problem also includes a batch processing version where you must process multiple test cases.

inputFormat

The input is read from standard input (stdin) and has the following format:

M
N_1
a1 a2 ... aN1
T_1
N_2
a1 a2 ... aN2
T_2
... (and so on for M test cases)

Where:

• M is the number of test cases.
• For each test case:
• N is the number of fruits.
• The next line contains N space-separated integers representing the health values of the fruits.
• T is the target health value.

outputFormat

For each test case, output a single integer on a new line representing the maximum sum of a contiguous subarray of fruits that does not exceed the target value \(T\). The output is written to standard output (stdout).

## sample

3
5
1 2 3 4 5
10
6
-1 2 3 -4 5 -3
5
4
5 -2 -3 2
4

10
5
2

</p>