#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

void upd(int &x, int y){
    if (x < y) x = y;
}


void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    int sum = 0;
    for (int i = 0; i < m; ++i){
        cin >> x[i];
        sum += x[i];
    }
    int flag = 0;
    if (flag){
        // x[i] = x[j];
        if (n >= m){
            cout << x[0] * m << endl;
            return;
        }
        if ((m - n) % 2 == 0) {
            cout << x[0] * n << endl;
            return;
        } else{
            cout << x[0] * (n - 1) << endl;
            return;
        }

    }
    if (m >= n){
        cout << sum << endl;
        return;
    }
    reverse(x.begin(), x.end());
    int inf = 1e18;


    int ans = 0;
    vector<int> y = x;
    sort(y.begin(), y.end());
    int mn = y[0];
    int mx = y.back();
    if (mn == mx){
        // x[i] = x[j];
        if (n >= m){
            cout << x[0] * m << endl;
            return;
        }
        if ((m - n) % 2 == 0) {
            cout << x[0] * n << endl;
            return;
        } else{
            cout << x[0] * (n - 1) << endl;
            return;
        }
    }
    int cmn = 0, cmx = 0;
    for (int i = 0; i < m; ++i){
        if (x[i] == mn) cmn++;
        else cmx++;
    }
    int cnt = n;
    for (int i = 0; i < m; ++i){
        if (cnt == n){
            cnt = n - 1;
            ans += x[i];
        } else if (cnt == 0){
            cnt = 1;
            ans -= x[i];
        } else{
            if (x[i] == mx){
                ans += x[i];
                cnt--;
            } else{
                if (cnt - 1 < cmx) {
                    ans -= x[i];
                    cnt++;
                } else{
                    ans += x[i];
                    cnt--;
                }
            }
        }
        if (x[i] == mx) cmx--;
        else cmn--;
    }
    cout << ans << endl;

//    vector<vector<int>> dp(m + 1, vector<int> (n + 1, -inf));
//    dp[0][n] = 0;
//    for (int i = 0; i < m; ++i){
//        for (int k = 0; k <= n; ++k){
//            if (k != 0){
//                upd(dp[i + 1][k - 1], dp[i][k] + x[i]);
//            }
//            if (k != n){
//                upd(dp[i + 1][k + 1], dp[i][k] - x[i]);
//            }
//        }
//    }
//    int ans = -inf;
//    for (int k = 0; k <= n; ++k){
//        upd(ans, dp[m][k]);
//    }
//    cout << ans << endl;
}



signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--){
        solve();
    }
}