#include <bits/stdc++.h>
using namespace std;
#define int long long

struct segtree {
    segtree *L, *R;
    int l, r, mx, lz;
    segtree(int lb, int rb) {
        l = lb; r = rb; mx = 0; lz = 0;
        if (l == r) return;
        L = new segtree(l, (l + r) / 2);
        R = new segtree((l + r) / 2 + 1, r);
    };

    void push() {
        mx += lz;
        if (l != r) {
            L -> lz += lz;
            R -> lz += lz;
        }
        lz = 0;
    }

    void add(int lb, int rb, int x) {
        push();
        if (l > rb || r < lb) return;
        if (lb <= l && r <= rb) {
            lz += x;
            push();
            return;
        }
        L -> add(lb, rb, x);
        R -> add(lb, rb, x);
        mx = min(L -> mx, R -> mx);
    }

    int get(int lb, int rb) {
        push();
        if (l > rb || r < lb) return (int)1e9;
        if (lb <= l && r <= rb) return mx;
        return min(L -> get(lb, rb), R -> get(lb, rb));
    };
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector < int > a(m);
    for (int i = 0; i < m; i++) cin >> a[i];
    reverse(begin(a), end(a));


    int sum = 0;
    for (int i = 0; i <  m; i++) sum += a[i];

    set < pair < int , int > > se;
    segtree *tree = new segtree(0, m);
    int c = 0;

    function < void(int) > add = [&](int i) {
        tree -> add(i, m - 1, 1);
        se.insert({a[i], i});
    };
    function < bool(int) > del = [&](int i) {
        se.erase(se.find({a[i], i}));
        if (tree -> get(i, m - 1) < 2) return false;
        tree -> add(i, m - 1, -2);
        return true;
    };

    for (int i = 0, t = n; i < m; i++) {
        if (t > 0) {
            t--;
            add(i);
            continue;
        }
        while (se.size() > 0) {
            int mn = se.begin() -> first, p = se.begin() -> second;
            if (mn >= a[i]) break;
            if (!del(p)) {
                continue;
            } else {
                c += mn;
                t++;
                break;
            }
        }
        if (t == 0) {
            c += a[i];
            t++;
        }
    }
    cout << sum - c * 2 << '\n';



//    vector < int > dp(n + 1, -1e18), ndp(n + 1);
//    dp[0] = 0;
//    for (int i = 0; i < m; i++) {
//        for (int j = 0; j <= n; j++) ndp[j] = -1e18;
//        for (int j = 1; j <= n; j++)
//            ndp[j - 1] = max(ndp[j - 1], dp[j] - a[i]);
//        for (int j = 0; j < n; j++)
//            ndp[j + 1] = max(ndp[j + 1], dp[j] + a[i]);
//        swap(dp, ndp);
//        for (int i = 0; i <= n; i++) cout << dp[i] << ' ';
//        cout << endl;
//    }
//    for (int i = 0; i <= n; i++) cout << i << ' ' << dp[i] << endl;
//    cout << *max_element(begin(dp), end(dp)) << '\n';
}

main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    while (n--) solve();

}
