Maximum Sum

Description:

Input:

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines:

• the first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 99999$$$; $$$2k < n$$$) — the number of elements and operations, respectively.
• the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$; all $$$a_i$$$ are different) — the elements of the array.

Additional constraint on the input: the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.

Output:

For each test case, print one integer — the maximum possible sum of elements in the resulting array.

Sample Input:

6
5 1
2 5 1 10 6
5 2
2 5 1 10 6
3 1
1 2 3
6 1
15 22 12 10 13 11
6 2
15 22 12 10 13 11
5 1
999999996 999999999 999999997 999999998 999999995

Sample Output:

21
11
3
62
46
3999999986

Note:

In the first testcase, applying the first operation produces the following outcome:

• two minimums are $$$1$$$ and $$$2$$$; removing them leaves the array as $$$[5, 10, 6]$$$, with sum $$$21$$$;
• a maximum is $$$10$$$; removing it leaves the array as $$$[2, 5, 1, 6]$$$, with sum $$$14$$$.

$$$21$$$ is the best answer.

In the second testcase, it's optimal to first erase two minimums, then a maximum.