You are given an array a1,a2,…,an, 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. Input The first line contains one integer t (1≤t≤104) — the number of test cases. Each test case consists of two lines: the first line contains two integers n and k (3≤n≤2⋅105; 1≤k≤99999; 2k<n) — the number of elements and operations, respectively. the second line contains n integers a1,a2,…,an (1≤ai≤109; all ai are different) — the elements of the array. Additional constraint on the input: the sum of n does not exceed 2⋅105. Output For each test case, print one integer — the maximum possible sum of elements in the resulting array.

这是一道贪心算法的题目。我们可以将数组 a 排序，然后每次操作时，选择最小的两个元素进行删除，或者选择最大的元素进行删除。根据贪心的思想，我们应该优先选择最小的元素进行删除，因为这样可以保留更多的大元素，从而获得更大的总和。因此，我们可以考虑使用一个小根堆来维护当前数组中最小的两个元素，每次操作时，从堆中取出最小的两个元素进行删除，并将删除后的元素插入堆中。当堆中元素个数不足两个时，我们就从数组中选择最大的元素进行删除。

具体实现时，我们可以使用一个变量 sum 记录当前数组中所有元素的总和，使用一个变量 min_sum 记录当前堆中最小的两个元素的和，使用一个变量 max_num 记录当前数组中最大的元素。每次操作时，如果堆中元素不足两个，就删除最大的元素，否则就从堆中取出最小的两个元素进行删除。删除元素时，需要将 sum 减去被删除元素的值，并将删除后的元素插入堆中。最终，返回 sum 减去 min_sum 即可。

时间复杂度为 O(k log n)。