No submission language available for this problem.

Description

Input

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le n$) — the number of traps and the number of jump overs that you are allowed to make.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — base damage values of all traps.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case output a single integer — the minimal total damage that it is possible to get if you are allowed to jump over no more than $k$ traps.

Samples

5
4 4
8 7 1 4
4 1
5 10 11 5
7 5
8 2 5 15 11 2 8
6 3
1 2 3 4 5 6
1 1
7

0
21
9
6
0

Note

In the first test case it is allowed to jump over all traps and take $0$ damage.

In the second test case there are $5$ ways to jump over some traps:

1. Do not jump over any trap.

   Total damage: $5 + 10 + 11 + 5 = 31$.

2. Jump over the $1$-st trap.

   Total damage: $\underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29$.

3. Jump over the $2$-nd trap.

   Total damage: $5 + \underline{0} + (11 + 1) + (5 + 1) = 23$.

4. Jump over the $3$-rd trap.

   Total damage: $5 + 10 + \underline{0} + (5 + 1) = 21$.

5. Jump over the $4$-th trap.

   Total damage: $5 + 10 + 11 + \underline{0} = 26$.

To get minimal damage it is needed to jump over the $3$-rd trap, so the answer is $21$.

In the third test case it is optimal to jump over the traps $1$, $3$, $4$, $5$, $7$:

Total damage: $0 + (2 + 1) + 0 + 0 + 0 + (2 + 4) + 0 = 9$.