A15881 | Maximum Sum

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.