#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ld = long double;

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

ll rand1(ll a, ll b) {
    return uniform_int_distribution<ll> (a, b) (gen);
}

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<ll> x(m);
    set<ll> tot;
    for (auto &i : x) {
        cin >> i;
        tot.insert(i);
    }
    reverse(x.begin(), x.end());
//    if (tot.size() == 1) {
//        if (m <= n) {
//            cout << x[0] * m;
//        } else {
//            cout << x[0] * (n - ((m - n) % 2));
//        }
//        return;
//    }
    ll a = *tot.begin(), b = *tot.rbegin();
    ll sum = 0, bal = 0;
    for (ll i = 0; i < m; i++) {
        if (bal + m - i <= n) {
            sum += x[i];
            bal++;
            continue;
        }
        if (x[i] == a) {
            if (bal > 0) {
                sum -= a;
                bal--;
            } else {
                sum += a;
                bal++;
            }
        } else {
            if (bal < n) {
                sum += b;
                bal++;
            } else {
                sum -= b;
                bal--;
            }
        }
    }
//    ll maxb = ((m <= n) ? m : (n - (m - n) % 2));
//    sum += (maxb - bal) * a;
    cout << sum;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t12 = 1;
    cin >> t12;
    while (t12--) {
        solve();
        cout << '\n';
    }
    return 0;
}