题目描述

在一场激动人心的太空探险中，你指挥着一支由不同种类的星际飞船组成的舰队，每种飞船都有其独特的能量值。你的任务是通过执行一系列精心策划的操控，使得舰队的总能量值最大化。

你需要执行恰好 $k$ 次操控，每次操控你可以选择以下两种策略之一：

你的目标是计算在执行了 $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$ 。

对于每个测试用例，输出一个整数 —— 在执行了 $k$ 次操控后，舰队剩余飞船的能量值之和的最大可能值。

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

在第一个测试用例中，选择移除能量值最低的两艘飞船，即 $1$ 和 $2$ ，剩余舰队为 $[5, 10, 6]$ ，其能量值之和为 $21$ ；若选择移除能量值最高的飞船 $10$ ，则剩余舰队为 $[2, 5, 1, 6]$ ，能量值之和为 $14$ 。因此， $21$ 是最佳答案。

在第二个测试用例中，首先移除能量值最低的两艘飞船，然后移除能量值最高的一艘飞船是最优选择。