2318: 最高金额
[Creator : ]
Description
给你一个数组 a1,a2,…,an，其中所有元素都是不同的。
你必须对它进行 k 次操作。在每个操作过程中，你都要做以下两个操作中的 一 个(你自己选择做哪个)：
-
在数组中找到两个最小元素，并删除它们；
-
在数组中找到个最大元素
Input
第一行包含一个整数 t ($1 \le n \le 10^4$ ) - 测试用例的数量。
每个测试用例由两行组成：
- 第一行包含两个整数 n 和 k （$3 \le n \le 10^3$ ; 1 ≤ k ≤ 499；2 * k < n ）--分别是元素数和操作数。
- 第二行包含 n 个整数 $a_1, a_2,...., a_n$ （ 1 ≤ a_i ≤ 10^9 ；所有 a_i 都不同）--数组的元素。
每个测试用例由两行组成：
- 第一行包含两个整数 n 和 k （$3 \le n \le 10^3$ ; 1 ≤ k ≤ 499；2 * k < n ）--分别是元素数和操作数。
- 第二行包含 n 个整数 $a_1, a_2,...., a_n$ （ 1 ≤ a_i ≤ 10^9 ；所有 a_i 都不同）--数组的元素。
Output
对于每个测试用例，打印一个整数 - 结果数组中元素的最大可能总和。
Sample Input Copy
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
Sample Output Copy
21
11
3
62
46
3999999986
HINT
在第一个测试案例中，执行第一个操作会产生以下结果：
- 两个最小值分别为 1 和 2 ，删除后数组为 [5, 10, 6] ，总和为 21 ；
- 最大值为 10 ；删除后数组为 [2, 5, 1, 6] ，总和为 14 。
21 是最佳答案。
在第二个测试案例中，最好先删除两个最小值，然后再删除一个最大值。
第五个测试样例中 最优解是去掉22 去掉15 .
- 两个最小值分别为 1 和 2 ，删除后数组为 [5, 10, 6] ，总和为 21 ；
- 最大值为 10 ；删除后数组为 [2, 5, 1, 6] ，总和为 14 。
21 是最佳答案。
在第二个测试案例中，最好先删除两个最小值，然后再删除一个最大值。
第五个测试样例中 最优解是去掉22 去掉15 .