#ifndef SEREGA
#include <bits/allocator.h>
#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("O3,no-stack-protector")
#endif
#include <bits/stdc++.h>
using namespace std;
#define int int64_t


int n, m;
vector<int> x;
vector<int> a;
int answer = 0;
map<pair<vector<int>, int>, int> cache;
int dfs(vector<int> &ssf, int index) {
    if (cache.contains({ssf, index})) return cache[{ssf, index}];
    if (index == m) {
        return accumulate(ssf.begin(), ssf.end(), int(0));
    }
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        ssf[i] = x[index] - ssf[i];
        mx = max(mx, dfs(ssf, index + 1));
        ssf[i] = x[index] - ssf[i];
    }
    return cache[{ssf, index}] = mx;
}
void solve() {
    cin >> n >> m;
    x.assign(m, {});
    a.assign(n, {});
    map<int, int> cnt;
    for (int i = 0; i < m; ++i) {
        cin >> x[i];
        cnt[x[i]]++;
    }
    int mx = *max_element(x.begin(), x.end());
    if (m <= n) {
        cout << accumulate(x.begin(), x.end(), 0ll) << '\n';
        return;
    }
    if (cnt.size() == 1) {
        cout << ((m - n) & 1 ? x[0] * (n - 1) : x[0] * n) << '\n';
        return;
    }
    int timer = 0;
    int badtimer = n - 1;
    for (int i = 0; i < m; ++i) {
        if (x[i] == mx) {
            if (timer != n) {
                if (a[timer] != 0) {
                    if (timer != n - 1) {
                        a[timer] = a[timer + 1] = 0;
                        badtimer = timer + 1;
                    }
                }
                a[timer] = x[i] - a[timer];
                timer++;
                continue;
            } else {
                a[timer - 1] = x[i] - a[timer - 1];
            }
        } else {
            if (badtimer != -1) {
                a[badtimer--] = x[i];
            } else {
                a[badtimer + 1] = x[i] - a[badtimer + 1];
            }
        }
    }
    cout << accumulate(a.begin(), a.end(), 0ll) << endl;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) solve();
}