codeforces#P1832B. Maximum Sum

Maximum Sum

Description

You are given an array $a_1, a_2, \dots, a_n$, where all elements are different.

You have to perform exactly $k$ operations with it. During each operation, you do exactly one of the following two actions (you choose which to do yourself):

  • find two minimum elements in the array, and delete them;
  • find the maximum element in the array, and delete it.

You have to calculate the maximum possible sum of elements in the resulting array.

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$.

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

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.

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
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.