# Question

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.

Example
input
Copy
65 12 5 1 10 65 22 5 1 10 63 11 2 36 115 22 12 10 13 116 215 22 12 10 13 115 1999999996 999999999 999999997 999999998 999999995
output
Copy
21
11
3
62
46
3999999986

Note

In the first testcase, applying the first operation produces the following outcome:

• two minimums are $1$ and $2$; removing them leaves the array as $\left[5,10,6\right]$, with sum $21$;
• a maximum is $10$; removing it leaves the array as $\left[2,5,1,6\right]$, with sum $14$.

$21$ is the best answer.

In the second testcase, it's optimal to first erase two minimums, then a maximum.

# Explanation

Take array arr and n , m

then sort the array arr

calculate prefix sum as s

then remove the array by rm = s[n-(k-i)] - s[2*i];

and make the answer as ans = max(ans,rm)

print final aswer as cout<<ans<<endl;

# Code

#include<bits/stdc++.h>

using namespace std;

#define test     long long T;cin>>T;while(T--)

#define all(x) (x).begin(), (x).end()

#define ll     long long

const int N = 2e5 + 5;

int arr[N];

ll s[N];

void solve()

{

int n,k; cin>>n>>k;

for(int i=1;i<=n;i++) cin>>arr[i];

sort(arr+1,arr+1+n);

for(int i=1;i<=n;i++){

s[i] = s[i-1] + arr[i];

}

ll ans=0;

for(int i=0;i<=k;i++){

ll tp = s[n-(k-i)] - s[2*i];

ans = max(ans,tp);

}

cout<<ans<<endl;

}

signed main() {

test

//(if you want to take the more test cases you may uncomment it out)

solve();

}