给定一个数组 $$$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
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
21 11 3 62 46 3999999986
注意
在第一个测试用例中,应用第一个操作会产生以下结果:
- 两个最小值为 $$$1$$$ 和 $$$2$$$;删除它们后,数组为 $$$[5, 10, 6]$$$,总和为 $$$21$$$;
- 最大值为 $$$10$$$;删除它后,数组将变为 $$$[2, 5, 1, 6]$$$,总和为 $$$14$$$。
$$$21$$$ 是最佳答案。
在第二个测试用例中,最好首先删除两个最小值,然后删除一个最大值。