B_Maximum_Sum.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = a; i < b; i++)

void solve() {

}
int main() {
    fastio;

    int t;
    cin >> t;
    while (t--) {
        int n , x;
        cin>>n>>x;
        vector<int> arr(n+1, 0);

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

        }
        sort(arr.begin() , arr.end());
        vector<long long > pr(n+1);
        pr[0] = 0;
        for(int i=1;i<=n;i++){
            pr[i]+=(pr[i-1] + arr[i]);
        }
        long long ans = 0;
        for(int i=0;i<=x;i++){
            ans = max(ans , pr[n-(x-i)] - pr[2*i]);
        }
        cout<<ans<<endl;
    }

    return 0;
}





/*
int main() {
    fastio;

    int t;
    cin >> t;
    while (t--) {
        int n , x;
        cin>>n>>x;
        vector<int> arr(n);
        long long sum = 0;
        long long rem = 0;
        for(int i=0;i<n;i++){
             cin>>arr[i];
             sum+=arr[i];
        }
        sort(arr.begin() , arr.end());
        int two = 2*x-1 , one  = n-x;
        long long check = 0;

        for(int i=0;i<x;i++){
           if(arr[two] + arr[two-1]>=arr[one]){
            check+=(arr[two] + arr[two-1]);
            two-=2;
           }
           else{
            check+=(arr[one]);
            one--;
           }
        }
        int s = 0 , e = n-1;
        //cout<<check<<endl;

        for(int i=0;i<x;i++){
            //cout<<arr[s]<<" "<<arr[s+1];
            rem+=arr[s] + arr[s+1];
            s+=2;
            rem+=arr[e];
            e--;
        }
        // cout<<rem<<endl;
        // cout<<sum<<endl;
        cout<<sum - rem + check<<endl;
    }

    return 0;
}

*/