Longest Subarray Sum with Upper Bound

You are given an array of ( n ) integers and an integer ( k ). Your task is to find a contiguous subarray whose sum is less than or equal to ( k ) and has the maximum possible length. If there are multiple subarrays meeting the maximum length criteria, choose the one with the smallest sum. In other words, if there exist several subarrays of length ( L ) whose sums do not exceed ( k ), you must output the minimum sum among them. This problem requires processing multiple test cases efficiently.

inputFormat

The input begins with a line containing an integer ( T ), denoting the number of test cases. Each test case consists of three lines:\

1. The first line contains an integer ( n ), the number of elements in the array.\
2. The second line contains ( n ) space-separated integers denoting the elements of the array.\
3. The third line contains an integer ( k ), the upper bound for the subarray sum.

outputFormat

For each test case, output one line containing a single integer — the smallest sum of the longest contiguous subarray whose sum is less than or equal to ( k ).## sample

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

6
4
10