CF1832B Maximum Sum

You are given an array $ a_1, a_2, \dots, a_n $ , where all elements are different. You have to perform exactly $ k $ operations with it. During each operation, you do exactly one of the following two actions (you choose which to do yourself): - find two minimum elements in the array, and delete them; - find the maximum element in the array, and delete it. You have to calculate the maximum possible sum of elements in the resulting array.

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of two lines: - the first line contains two integers $ n $ and $ k $ ( $ 3 \le n \le 2 \cdot 10^5 $ ; $ 1 \le k \le 99999 $ ; $ 2k < n $ ) — the number of elements and operations, respectively. - the second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ; all $ a_i $ are different) — the elements of the array. Additional constraint on the input: the sum of $ n $ does not exceed $ 2 \cdot 10^5 $ .

For each test case, print one integer — the maximum possible sum of elements in the resulting array.

In the first testcase, applying the first operation produces the following outcome: - two minimums are $ 1 $ and $ 2 $ ; removing them leaves the array as $ [5, 10, 6] $ , with sum $ 21 $ ; - a maximum is $ 10 $ ; removing it leaves the array as $ [2, 5, 1, 6] $ , with sum $ 14 $ . $ 21 $ is the best answer. In the second testcase, it's optimal to first erase two minimums, then a maximum.