#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <string>

#define len(v) (int)((v).size())
#define ss second
#define ff first


typedef long long ll;

using namespace std;

const ll inf = 1e9;

struct obj {
	ll x;
	int px;
	obj(int x, int i) : x(x), px(i) {}
	obj() : obj(inf, -1) {}

	static obj merge(const obj& a, const obj& b) {
		obj res;
		res.x = min(a.x, b.x);
		res.px = a.px;
		if (a.x != res.x) res.px = b.px;
		return res;
	}
};

struct info {
	ll x;
	info(int x) : x(x) {}
	info() : info(0) {}

	static void upd(obj& a, const info& b, int ln) {
		a.x += b.x;
	};
	static void upd(info& a, const info& b, int ln) {
		a.x += b.x;
	};
	bool is_empty() {
		return x == 0;
	}
};

struct ST {
	static const int sz = 1 << 20;
	obj tree[sz];
	info add[sz];

	void build(int v, int l, int r, vector<int>& a) {
		add[v] = 0;
		if (r - l == 1) {
			tree[v] = obj(a[l], l);
			return;
		}
		int m = (l + r) / 2;
		build(v * 2, l, m, a);
		build(v * 2 + 1, m, r, a);
		tree[v] = obj::merge(tree[v * 2], tree[v * 2 + 1]);
	}
	void push(int v, int l, int r) {
		if (add[v].is_empty()) return;

		if (r - l > 1) {
			info::upd(add[v * 2], add[v], r - l);
			info::upd(add[v * 2 + 1], add[v], r - l);
		}
		info::upd(tree[v], add[v], r - l);
		add[v] = info();
	}
	void upd(int v, int l, int r, int ql, int qr, info qx) {
		push(v, l, r);
		if (l >= qr || ql >= r) return;
		if (l >= ql && r <= qr) {
			add[v].upd(add[v], qx, r - l);
			push(v, l, r);
			return;
		}
		int m = (l + r) / 2;
		upd(v * 2, l, m, ql, qr, qx);
		upd(v * 2 + 1, m, r, ql, qr, qx);
		tree[v] = obj::merge(tree[v * 2], tree[v * 2 + 1]);
	}
	obj get(int v, int l, int r, int ql, int qr) {
		push(v, l, r);
		if (l >= qr || ql >= r) return obj();
		if (l >= ql && r <= qr) return tree[v];
		int m = (l + r) / 2;
		obj r1 = get(v * 2, l, m, ql, qr);
		obj r2 = get(v * 2 + 1, m, r, ql, qr);
		return obj::merge(r1, r2);
	}
} tx, tpr;

void solve() {
	int n, m;
	cin >> n >> m;

	vector<int> x(m);
	for (int i = 0; i < m; ++i) {
		cin >> x[i];
	}

	reverse(x.begin(), x.end());

	tx.build(1, 0, m, x);

	vector<int> a(m, 1);
	for (int i = 1; i < m; ++i) {
		a[i] = a[i - 1] + 1;
	}
	tpr.build(1, 0, m, a);

	int cnt = 0;
	ll ans = 0;
	int l = 1;
	for (int i = 0; i < m; ++i) {
		ans += x[i];
		obj res = tpr.get(1, 0, m, i, i + 1);

		while (res.x > n) {
			obj f = tx.get(1, 0, m, l, i + 1);
			tpr.upd(1, 0, m, f.px, m, -2);
			tx.upd(1, 0, m, f.px, f.px + 1, inf);
			ans -= 2 * f.x;
			
			a[f.px] = -1;

			obj rr = tpr.get(1, 0, m, l, m);
			while (rr.x <= 1) {
				l = rr.px + 1;
				rr = tpr.get(1, 0, m, l, m);
			}
			res = tpr.get(1, 0, m, i, i + 1);
		}
	}
	cout << ans << '\n';

}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cout.precision(30);

	int t = 1;
    cin >> t;
	while (t--) solve();
}



