//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

using ll = long long;
using ld = long double;
const ll inf = 1e18;

#define all(a) a.begin(), a.end()
#define pb push_back

using namespace std;
using namespace literals;
//using namespace __gnu_pbds;

//using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
//gp_hash_table<ll, ll> s;

mt19937 rnd;

void solve();
void precalc();

int main() {
#ifdef LOCAL:
    freopen("INPUT.TXT", "r", stdin);
    freopen("OUTPUT.TXT", "w", stdout);
    const auto start = chrono::steady_clock::now();
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    precalc();
    bool cfmode = true;
    if(cfmode) {
        ll t;
        cin >> t;
        while(t--) {
            solve();
        }
    } else {
        solve();
    }
#ifdef LOCAL:
    const auto end = chrono::steady_clock::now();
    cout << "\n";
    cout << fixed << setprecision(10) << "xxxTIMExxx: " << (end - start) / 1ms;
#endif
}

void precalc() {

}

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(m);
    ll t1 = -inf, t2 = inf;
    for(int i = 0; i < m; i++) {
        cin >> a[i];
        t1 = max(t1, a[i]);
        t2 = min(t2, a[i]);
    }
    if(t1 == t2) {
        ll x = a[0];
        if(n >= m) {
            cout << x * m;
        } else {
            m -= n;
            cout << x * n - x * (m % 2);
        }
        cout << "\n";
    } else {
        vector<pair<ll, ll>> suf(m, {0, 0});
        for(int i = m - 1; i >= 0; i--) {
            if(i != m - 1) {
                suf[i].first += suf[i + 1].first;
                suf[i].second += suf[i + 1].second;
            }
            if(a[i] == t1) {
                suf[i].first++;
            } else {
                suf[i].second++;
            }
        }
        ll ans = 0;
        ll balance = 0;
        for(int i = 0; i < m; i++) {
            if(a[i] == t1) {
                if(balance < n) {
                    balance++;
                    ans += a[i];
                } else {
                    balance--;
                    ans -= a[i];
                }
            } else {
                if(balance + suf[i].first + suf[i].second <= n) {
                    if(balance < n) {
                        balance++;
                        ans += a[i];
                    } else {
                        balance--;
                        ans -= a[i];
                    }
                } else {
                    if(balance > 0) {
                        balance--;
                        ans -= a[i];
                    } else {
                        balance++;
                        ans += a[i];
                    }
                }
            }
        }
        cout << ans << "\n";
    }
}

