题目描述

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

你需要对该数组恰好进行 $k$ 次操作。每次操作，你可以选择以下两种操作之一（任选其一）：

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

请你计算操作结束后，数组中剩余元素的最大可能和。

输入格式

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

每个测试用例包含两行：

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

输入还满足一个额外条件：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示操作结束后数组中剩余元素的最大可能和。

说明/提示

在第一个测试用例中，执行第一次操作后的结果如下：

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

$21$ 是最优答案。

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

由 ChatGPT 4.1 翻译

样例

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