#ifdef ONPC
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

bool chmax(ll& a, ll b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int MAXN = 303030;

int cost[MAXN], del[MAXN];
int segtree[1 << 20] = {};
int lz[1 << 20] = {};

void push(int x, int l, int r) {
    if (lz[x] == 0) return;

    if (l + 1 != r) {
        lz[2 * x + 1] += lz[x];
        lz[2 * x + 2] += lz[x];
    }

    segtree[x] += lz[x];
    lz[x] = 0;
}

int get(int lq, int rq, int x, int l, int r) {
    if (rq <= l || r <= lq) return 0;
    push(x, l, r);
    if (lq <= l && r <= rq) return segtree[x];

    int m = (l + r) / 2;
    return max(get(lq, rq, 2 * x + 1, l, m), get(lq, rq, 2 * x + 2, m, r));
}

void update(int lq, int rq, int v, int x, int l, int r) {
    if (lq <= l && r <= rq) {
        lz[x] += v;
        push(x, l, r);
        return;
    }
    push(x, l, r);
    if (rq <= l || r <= lq) return;

    int m = (l + r) / 2;
    update(lq, rq, v, 2 * x + 1, l, m);
    update(lq, rq, v, 2 * x + 2, m, r);
    segtree[x] = max(segtree[2 * x + 1], segtree[2 * x + 2]);
}

int get_first(int lq, int v, int x, int l, int r) {
    push(x, l, r);
    if (r <= lq || segtree[x] <= v) return -1;
    if (l + 1 == r) return l;

    int m = (l + r) / 2;
    int res = get_first(lq, v, 2 * x + 1, l, m);
    if (res == -1) res = get_first(lq, v, 2 * x + 2, m, r);
    return res;
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> cost[i], del[i] = 0, assert(cost[i] >= 0);
    reverse(cost + 1, cost + m + 1);

    for (int i = 0; i < min(4 * n, 1 << 20); i++) segtree[i] = lz[i] = 0;

    int cur = 0;
    set<array<int, 2>> now;

    ll ans = 0;
    for (int i = 1; i <= m; i++) ans += cost[i], update(i, m + 1, 1, 0, 0, m + 1);

    while (true) {
        int r = get_first(0, n, 0, 0, m + 1);
        if (r == -1) break;
        int mn = 2e9, id = -1;
        for (int i = 1; i <= r; i++) {
            if (del[i] || get(i, i + 1, 0, 0, m + 1) == 1) continue;
            if (cost[i] <= mn) {
                mn = cost[i];
                id = i;
            }
        }

        ans -= 2 * mn;
//        now.erase(now.begin());
        update(id, m + 1, -2, 0, 0, m + 1);
        del[id] = 1;
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) solve();

    return 0;
}
