#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ve vector
#define pb push_back
ll const inf = 1e9 + 3;

ll const INF = 1e18;

struct Node {
    ll val = 0;
    ll added = 0;
    bool is_added = false;
};

ve<Node> tree;

void build(ll v, ll tl, ll tr) {
    if (tr - tl == 1) {

        return;
    }
    ll m = (tl + tr) / 2;
    build(2 * v, tl, m);
    build(2 * v + 1, m, tr);
}

void add_to_Node(ll v, ll tl, ll tr, ll val) {
    tree[v].val += (tr - tl) * val;
    tree[v].added += val;
    tree[v].is_added = true;
}

void push(ll v, ll tl, ll tr) {
    if (tree[v].is_added) {
        ll m = (tl + tr) / 2;
        add_to_Node(2 * v, tl, m, tree[v].added);
        add_to_Node(2 * v + 1, m, tr, tree[v].added);
        tree[v].added = 0;
        tree[v].is_added = false;
    }
}

void Add(ll v, ll tl, ll tr, ll ql, ll qr, ll val) {
    if (tl >= qr || tr <= ql)
        return;
    if (tr == qr && tl == ql) {
        add_to_Node(v, tl, tr, val);
        return;
    }
    ll m = (tl + tr) / 2;
    push(v, tl, tr);
    Add(2 * v, tl, m, ql, min(m, qr), val);
    Add(2 * v + 1, m, tr, max(m, ql), qr, val);
    tree[v].is_added = 0;
    tree[v].val = tree[2 * v].val + tree[2 * v + 1].val;
}

ll get_sum(ll v, ll tl, ll tr, ll ql, ll qr) {
    if (tr == qr && tl == ql) {
        return tree[v].val;
    }
    push(v, tl, tr);
    ll m = (tl + tr) / 2;
    ll s1 = get_sum(2 * v, tl, m, ql, min(qr, m));
    ll s2 = get_sum(2 * v + 1, m, tr, max(m, qr), ql);
    return s1 + s2;
}

int main() {
#ifdef DEBUG_Q
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll t;
    cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        ll i, j;
        ll x[m];
        ll mn = INF;
        ll mx = -INF;
        for (i = 0; i < m; i++) {
            cin >> x[i];
            mn = min(mn, x[i]);
            mx = max(mx, x[i]);
        }
        if (mn == mx) {
            if (n >= m) {
                cout << m * x[0] << endl;
            } else {
                if ((m - n) % 2 == 0) {
                    cout << n * x[0] << endl;
                } else {
                    cout << (n - 1) * x[0] << endl;
                }
            }
            continue;
        }
        ll nb_of_min = 0;
        ll sum = 0;
        if (n >= m) {
            for (i = 0; i < m; i++) {
                sum += x[i];
            }
            cout << sum << endl;
            continue;
        }
        for (i = m - 1; i >= 0; i--) {
            if (nb_of_min == 0) {
                nb_of_min++;
                sum += x[i];
                continue;
            }
            if (nb_of_min == n) {
                nb_of_min--;
                sum -= x[i];
                continue;
            }
            if (x[i] == mx) {
                sum += mx;
                nb_of_min--;
            } else {
                sum -= mn;
                nb_of_min++;
            }
        }
        if (nb_of_min < n) {
            if (n % 2 == m % 2) {
                sum += (n - nb_of_min) * mn;
            } else {
                sum += (n - 1 - nb_of_min) * mn;
            }
        }
        cout << sum << endl;
    }
}
