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

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using str = string;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
const ll INF = 1e18, MOD = 1e9 + 7;
#define int long long

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
        cout << "\n";
    }
}

struct seg_tree {
    vector<pair<int, int>> t;
    int siz;

    seg_tree(int n) {
        t.resize(4 * n + 5);
        siz = n;
    }

    void push(int v) {
        t[2 * v].second += t[v].second;
        t[2 * v + 1].second += t[v].second;
        t[v].second = 0;
    }

    void add(int v, int l, int r, int ql, int qr, int x) {
        if (ql == l && qr == r) {
            t[v].second += x;
            return;
        }
        push(v);
        int qm = (ql + qr) / 2;
        if (r <= qm) {
            add(2 * v, l, r, ql, qm, x);
        } else if (l >= qm) {
            add(2 * v + 1, l, r, qm, qr, x);
        } else {
            add(2 * v, l, qm, ql, qm, x);
            add(2 * v + 1, qm, r, qm, qr, x);
        }
        t[v].first = min(t[2 * v].first + t[2 * v].second, t[2 * v + 1].first + t[2 * v + 1].second);
    }

    int get(int v, int l, int r, int ql, int qr) {
        if (ql == l && qr == r) {
            return t[v].first + t[v].second;
        }
        push(v);
        t[v].first = min(t[2 * v].first + t[2 * v].second, t[2 * v + 1].first + t[2 * v + 1].second);
        int qm = (ql + qr) / 2;
        if (r <= qm) {
            return get(2 * v, l, r, ql, qm);
        } else if (l >= qm) {
            return get(2 * v + 1, l, r, qm, qr);
        } else {
            return min(get(2 * v, l, qm, ql, qm),
                       get(2 * v + 1, qm, r, qm, qr));
        }
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m + 1);
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
    }
    int sum = 0;
    for (int i = 1; i <= m; ++i) {
        sum += a[i - 1];
    }
    reverse(a.begin(), a.end());
    auto x = seg_tree(m + 1);
    for (int i = 1; i <= m; ++i) {
        x.add(1, i, i + 1, 0, m + 1, i);
    }
    set<pair<int, int>> d;
    int b = 0;
    for (int i = 1; i <= m; ++i) {
        d.insert({a[i], i});
        b++;
        if (b == n + 1) {
            while ((int) d.size() > 0) {
                auto k = *d.begin();
                int u = x.get(1, k.second, m + 1, 0, m + 1);
                if (u < 2) {
                    d.erase(d.find(k));
                } else {
                    d.erase(d.find(k));
                    sum -= 2 * k.first;
                    x.add(1, k.second, m + 1, 0, m + 1, -2);
                    b -= 2;
                    break;
                }
            }
        }
    }
    cout << sum;
}