Maximizing Final Ability in Problem Solving

You start with an ability of 0. There are n problem banks. In the i-th bank, every problem has the same difficulty a_i (with infinitely many problems available from each bank).

You need to solve exactly m problems. For each problem you choose from among all available problems, your update rule is as follows. Let your current ability be w (initially 0). When you attempt a problem of difficulty d:

• If w ≥ d, you can solve the problem by "spending" your ability. In doing so your ability decreases by d (i.e. w becomes w - d).
• If w < d, you study the problem carefully and in the process your ability increases by d (i.e. w becomes w + d). Note that in this case your ability does not decrease.

Your goal is to maximize your final ability after solving exactly m problems. There are multiple independent queries (each starting with an initial ability of 0).

Hint: It is always beneficial to pick a problem whose difficulty is higher than your current ability (so that you gain the addition instead of subtracting) as long as one exists. Otherwise, you are forced to pick a problem with difficulty not exceeding your current ability, in which case it is optimal to subtract as little as possible.

Formally, let w be your current ability. If there exists a difficulty d in the set of available difficulties with d > w, then the optimal move is to choose the smallest such d (thus increasing your ability by d). Otherwise, you must choose a problem with difficulty at most w, and it is optimal to choose the minimum difficulty available (say, a_min) so that your ability decreases by as little as possible.

inputFormat

The input begins with an integer T denoting the number of queries. Each query is described as follows:

• The first line contains two integers n and m — the number of problem banks and the number of problems to solve.
• The second line contains n integers: a₁, a₂, ..., a_n — where each a_i denotes the difficulty of all problems in the i-th bank.

Note: Each query is independent and starts with an initial ability of 0.

outputFormat

For each query, output a single integer — the maximum final ability you can achieve after solving exactly m problems optimally.

sample

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

3
8
5