Magical Staff Power Level

You are given a sequence of M integers and an integer L. Your task is to compute the median of sums of all possible subsequences of length L. This median represents the "power level" of a magical staff.

Formally, let \( S \) be the set of all \( L \)-element subsequences of the given sequence, and let \( f(s) \) be the sum of the elements in a subsequence \( s \). You are required to compute the median of the multiset \( \{ f(s) : s \in S \} \). Use the standard definition of median: if the size of \( S \) is odd, the median is the middle element of the sorted sums, otherwise it is the average of the two middle elements. It is guaranteed that in all given test cases, the median will be an integer.

inputFormat

The input begins with an integer T indicating the number of test cases. Each test case is described over two lines:

1. The first line contains two space-separated integers: M (the number of elements in the sequence) and L (the length of the subsequences to consider).
2. The second line contains M space-separated integers representing the sequence.

Note: Input is provided via standard input (stdin).

outputFormat

For each test case, output a single line with the median of the sums of all possible subsequences of length L. The result should be printed to standard output (stdout).

## sample

2
5 3
1 2 3 4 5
4 2
4 1 3 2

9
5

</p>