#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>

const long long inf = (1ll << 63) - 1;
struct tree {
	struct lec {
		int min, push;
	};
	int h;
	std::vector<lec> d;
	void build(int n) {
		h = 1;
		while (h < n) {
			h <<= 1;
		}
		d.resize((h << 1) - 1, {0, 0});
	}
	void push(int i) {
		int j = (i << 1) + 1;
		d[j].min += d[i].push;
		d[j].push += d[i].push;
		++j;
		d[j].min += d[i].push;
		d[j].push += d[i].push;
		d[i].push = 0;
	}
	void add(int i, int tl, int tr, int ql, int qx) {
		if (tl >= ql) {
			d[i].push += qx;
			d[i].min += qx;
			return;
		}
		if (tr <= ql) {
			return;
		}
		push(i);
		const int j = (i << 1) + 1, tm = (tr + tl) >> 1;
		add(j, tl, tm, ql, qx);
		add(j + 1, tm, tr, ql, qx);
		d[i].min = std::min(d[j].min, d[j + 1].min);
	}
	int find(int i, int tl, int tr) {
		if (tl == tr - 1) {
			return tl;
		}
		push(i);
		const int j = (i << 1) + 1, tm = (tr + tl) >> 1;
		if (d[j + 1].min <= 1) {
			return find(j + 1, tm, tr);
		}
		return find(j, tl, tm);
	}
};
void solve() {
	int k, n;
	std::cin >> k >> n;
	std::vector<long long> a(n);
	for (int i = n - 1; i >= 0; --i) {
		std::cin >> a[i];
	}
	if (k == 1 || n == 1) {
		long long ans = 0;
		for (int i = n - 1; i >= 0; --i) {
			ans = a[i] - ans;
		}
		std::cout << ans << '\n';
		return;
	}
	tree t;
	t.build(n);
	std::set<std::pair<int, int>> mi;
	long long ans = 0;
	int d = 0;
	for (int i = 0; i < n; ++i) {
		t.add(0, 0, t.h, i, 1);
		mi.insert({ a[i], i });
		ans += a[i];
		if (d == k) {
			d -= 2;
			int p = std::min(t.find(0, 0, t.h), i - 1);
			while (mi.size() > 0 && (*mi.begin()).second <= p) {
				mi.erase(mi.begin());
			}
			t.add(0, 0, t.h, (*mi.begin()).second, -2);
			ans -= 2 * (*mi.begin()).first;
			mi.erase(mi.begin());
		}
		++d;
	}
	std::cout << ans << '\n';
}
int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}
}
