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

给你一个数组 $a_1, a_2, \dots, a_n$，其中所有元素互不相同。

你需要对该数组恰好执行 $k$ 次操作。每次操作中，你必须且仅能执行以下两种操作之一（由你自行选择）：

• 找出数组中两个最小的元素，并将它们删除；
• 找出数组中最大的元素，并将它删除。

你需要计算最终剩余数组中元素之和的最大可能值。

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例由两行组成：

• 第一行包含两个整数 $n$ 和 $k$（$3 \le n \le 2 \cdot 10^5$；$1 \le k \le 99999$；$2k \lt n$）—— 分别表示数组元素个数和操作次数；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$；所有 $a_i$ 互不相同）—— 表示数组的元素。

输入的额外约束：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一个整数——结果数组中元素的最大可能和。

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.

在第一个测试用例中，执行第一种操作得到如下结果：

• 两个最小值为 $1$ 和 $2$；移除它们后，数组变为 $[5, 10, 6]$，其元素和为 $21$；
• 一个最大值为 $10$；移除它后，数组变为 $[2, 5, 1, 6]$，其元素和为 $14$。

$21$ 是最优答案。

在第二个测试用例中，最优策略是先移除两个最小值，再移除一个最大值。