#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll q = 1;
    cin >> q;
    while (q--) {
        solve();
    }
}

const ll INF = 1e18;

struct seg_t {
    struct Node {
        ll mn = 0, dept = 0;
    };
    vector<Node> tree;
    void push(ll v, ll vl, ll vr) {
        tree[v].mn += tree[v].dept;
        if (vr - vl != 1) {
            tree[2 * v].dept += tree[v].dept;
            tree[2 * v + 1].dept += tree[v].dept;
        }
        tree[v].dept = 0;
    }
    void add(ll v, ll vl, ll vr, ll l, ll r) {
        if (vl >= r || vr <= l) {
            push(v, vl, vr);
            return;
        }
        if (vl >= l && vr <= r) {
            tree[v].dept--;
            push(v, vl, vr);
            return;
        }
        push(v, vl, vr);
        ll m = (vl + vr) / 2;
        add(2 * v, vl, m, l, r);
        add(2 * v + 1, m, vr, l, r);
        tree[v].mn = min(tree[2 * v].mn, tree[2 * v + 1].mn);
    }
    void change(ll v, ll vl, ll vr, ll pos, ll x) {
        push(v, vl, vr);
        if (vr - vl == 1) {
            tree[v].mn = x;
            return;
        }
        ll m = (vl + vr) / 2;
        push(2 * v, vl, m);
        push(2 * v + 1, m, vr);
        if (pos < m) {
            change(2 * v, vl, m, pos, x);
        } else {
            change(2 * v + 1, m, vr, pos, x);
        }
        tree[v].mn = min(tree[2 * v].mn, tree[2 * v + 1].mn);
    }
    ll get(ll v, ll vl, ll vr, ll l, ll r) {
        push(v, vl, vr);
        if (vl >= r || vr <= l) {
            return INF;
        }
        if (vl >= l && vr <= r) {
            return tree[v].mn;
        }
        ll m = (vl + vr) / 2;
        return min(get(2 * v, vl, m, l, r), get(2 * v + 1, m, vr, l, r));
    }
};

struct tr {
    vector<pair<ll, ll>> tree;
    void change(ll v, ll vl, ll vr, ll pos, ll x, ll id) {
        if (vr - vl == 1) {
            tree[v] = {x, -id};
            return;
        }
        ll m = (vl + vr) / 2;
        if (pos < m) {
            change(2 * v, vl, m, pos, x, id);
        } else {
            change(2 * v + 1, m, vr, pos, x, id);
        }
        tree[v] = min(tree[2 * v], tree[2 * v + 1]);
    }
    pair<ll, ll> get(ll v, ll vl, ll vr, ll l, ll r) {
        if (vl >= r || vr <= l) {
            return {INF, INF};
        }
        if (vl >= l && vr <= r) {
            return tree[v];
        }
        ll m = (vl + vr) / 2;
        return min(get(2 * v, vl, m, l, r), get(2 * v + 1, m, vr, l, r));
    }
};

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<ll> x(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i];
    }
    reverse(x.begin(), x.end());
    seg_t t;
    t.tree.resize(4 * m);
    tr tt;
    tt.tree.resize(4 * m);
    ll sm = 0, c = 0;
    for (int i = 0; i < m; i++) {
        t.change(1, 0, m, i, (i + 1) / 2 - c);
        tt.change(1, 0, m, i, x[i], -i);
        sm += x[i];
        if (2 * c < i + 1 - n) {
            ll lf = -1, rf = i;
            while (rf - lf > 1) {
                ll mid = (lf + rf) / 2;
                if (t.get(1, 0, m, mid, i + 1) > 0) {
                    rf = mid;
                } else {
                    lf = mid;
                }
            }
            ll id = tt.get(1, 0, m, rf, i + 1).second * -1;
            sm -= 2 * x[id];
            tt.change(1, 0, m, id, INF, INF);
            t.add(1, 0, m, id, i + 1);
            c++;
        }
    }
    cout << sm << '\n';
} 