← 返回题目列表

Codeforces · 1832/B

B. 最大总和

中文机器翻译题面 查看原题

给定一个数组 $$$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$$$ 是最佳答案。

在第二个测试用例中,最好首先删除两个最小值,然后删除一个最大值。