Alice and Bob are given an integer array $A$ of length $N$.

Alice chooses a binary string $B$ of length $N$ with exactly $K$ ones, and this string is fixed for the whole game.

At any moment, index $i$ is protected if and only if $B_i = 1$, and Bob may choose index $i$ if and only if $B_i = 0$.

Bob makes zero or more moves. Bob's score initially equals $0$.

In one move, Bob chooses an index $i$ such that:

• $B_i = 0$;
• $1 \le i \le |A|$.

Bob adds the current value $A_i$ to his score and removes this element from $A$. After each deletion, $|A|$ decreases by $1$, and the remaining elements of $A$ are re-indexed from $1$ to $|A|$.

Therefore, $B$ is applied to current index positions, not to fixed element identities. After shifts, the same element may become protected or removable.

If Bob chooses indices $P_1, P_2, \dots, P_m$ across moves, they must be non-increasing, that is,

$$P_1 \ge P_2 \ge \dots \ge P_m$$

Bob may choose the same index multiple times.

Alice wants to minimize Bob's score, and Bob wants to maximize it.

Find Bob's final score if both players play optimally.

Input

The input is given in the following format:

T
N K
A1 A2 ... AN
...

Constraints

• All input values are integers.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• It is guaranteed that the sum of $N$ over all test cases does not exceed $10^6$.
• It is guaranteed that the sum of $N^2$ over all test cases does not exceed $6000^2$.

Output

For each test case, output a single integer — Bob's final score.

Example

Input 1

6
5 2
4 -1 7 -3 2
4 0
-5 -2 -1 -3
4 4
2 -7 5 1
1 0
-1
2 1
0 1
3 1
1 -1 1

Output 1

7
0
0
0
1
1

Note

• Test case 1: Alice can choose $B = 10001$. Then, initially, the indices available to Bob are $2$, $3$ and $4$ with values $-1$, $7$ and $-3$. Bob can guarantee a score of $7$ by taking index $3$ once (adding value $7$). After that, every next chosen index must be at most $3$, so index $4$ cannot be chosen, and any further legal move adds a non-positive value. Alice can force that Bob cannot do better than $7$, so the answer is $7$.
• Test case 2: As $K = 0$, Alice has no choice, $B = 0000$. All indices are available to Bob, but every array value is negative. Any move would decrease Bob's score, so Bob's optimal play is to make no move. Therefore, the answer is $0$.
• Test case 3: As $K = N$, Alice has no choice, $B = 1111$. Every position is protected, so Bob has no legal move at all. Hence, Bob's score is $0$.