Maximum Subset Sum under a Threshold

You are given an array of integers and three parameters: (n) (the size of the array), (k) (the number of elements to choose), and (T) (a threshold). Your task is to select exactly (k) elements from the array such that their sum is as large as possible while not exceeding (T). If no such subset exists, output -1.

More formally, given an array (A) of (n) integers, find a subset (S\subseteq A) with (|S| = k) that maximizes (\sum_{x \in S} x) subject to (\sum_{x \in S} x \le T). If no valid subset exists, print -1.

Note: It is guaranteed that the number of elements (n) is small enough to allow an exhaustive search solution.

inputFormat

The first line of the input contains an integer (t) representing the number of test cases. Each test case consists of two lines:

• The first line contains three integers (n), (k), and (T) separated by spaces.
• The second line contains (n) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line containing the maximum possible sum of any subset of size (k) that is less than or equal to (T). If no valid subset exists, output -1.## sample

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

12
8
-1