### 问题描述 小明是一名勇敢的冒险家，他在一次探险途中发现了一组神秘的宝石，这些宝石的价值都不同。但是，他发现这些宝石会随着时间的推移逐渐失去价值，因此他必须在规定的次数内对它们进行处理。 小明想要最大化这些宝石的总价值。他有两种处理方式： 1. 选出两个最小的宝石，并将它们从宝石组中删除。 2. 选出最大的宝石，并将其从宝石组中删除。 现在，给你小明手上的宝石组，请你告诉他在规定的次数内，最大化宝石的总价值是多少。 ### 输入格式 第一行包含一个整数 $t$，表示数据组数。 对于每组数据，第一行包含两个整数 $n$ 和 $k$，表示宝石的数量和规定的处理次数。 第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$，表示每个宝石的价值。 ### 输出格式 对于每组数据，输出一个整数，表示在规定的次数内，最大化宝石的总价值。 ### 样例输入 ```txt 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 ``` ### 样例输出 ```txt 21 11 3 62 46 3999999986 ``` ### 样例说明 在第一个测试用例中，两个最小值是 $1$ 和 $2$，去掉它们，数组为 $[5，10，6]$，和为 $21$。而最大值为 $10$，去掉它，则数组为 $[ 2,5,1,6]$，和为 $14$。最优的操作为执行一次操作一，得到最好的答案为 $21$。 在第二个测试用例中，最优的处理结果先删除两个最小值，然后再删除一个最大值。 ### 评测数据规模 对于 $100$% 的评测数据，$1\leq t \leq 10, 3\leq n \leq 2 \cdot 10^5 ,1 \leq k \leq 99999,2k < n$。