#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef __int128 lll;
const ll inf = 2e18, mod = 1e9 + 7;

#define all(a) a.begin(),a.end()
#define F first
#define S second

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ifstream in("C:\\work\\untitled\\input.txt");

    ll test;cin>>test;
    while(test--){
        ll m,n;cin>>m>>n;
        vector<ll>x(n);
        ll mn=inf,mx=0;
        for(auto &i:x) {
            cin >> i;
            mn=min(mn,i);
            mx=max(mx,i);
        }
        if(mn==mx){
            m=min(m,n);
            cout<<mn*m-mn*((n-m)%2)<<'\n';
            continue;
        }
        reverse(all(x));
        ll ans=0,kl=0,pr=0;
        for(ll i=0;i<n;i++){
            if(pr<m){
                pr++;
                ans+=x[i];
                if(x[i]==mn)
                    kl++;
            }else{
                if(kl){
                    ans-=mn*2;
                    ans+=x[i];
                    kl--;
                    pr--;
                    if(x[i]==mn)
                        kl++;
                }else{
                    pr--;
                    ans-=x[i];
                }
                if(pr==1)
                    kl=0;
            }
        }
        cout<<ans<<'\n';
    }
}
