Maximum Sum of Three Numbers Under a Limit

You are given an array of N integers and an integer K. Your task is to find three distinct elements in the array whose sum is as large as possible but does not exceed K. If there is no such combination, output -1.

Problem Details:

• Choose any three distinct numbers from the given array.
• Among all the possible combinations whose sum is less than or equal to K, find the one with the maximum sum.
• If no three-number combination has a sum ≤ K, print -1.

The problem may be solved by checking all possible triples. In mathematical terms, if the array is A = [a_1, a_2, \dots, a_N], find

[ \max_{1 \le i < j < k \le N} { a_i + a_j + a_k \ \mid \ a_i + a_j + a_k \le K }]

If no valid triple exists, return -1.

inputFormat

The first line contains an integer T — the number of test cases. Each test case consists of two lines:

• The first line of each test case contains two integers N and K, where N is the size of the array and K is the target upper bound.
• The second line contains N space-separated integers representing the array elements.

outputFormat

For each test case, output one line containing a single integer — the maximum sum of any three distinct numbers in the array that is less than or equal to K. If no such combination exists, output -1.

4
5 10
2 3 5 7 11
4 20
1 8 9 15
3 1
10 20 30
3 60
10 20 30

10
18
-1
60