#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <ctime>
#include <chrono>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <deque>
#include <bitset>
using namespace std;
mt19937_64 rnd(time(NULL));

const long long INF = 1e18, MOD = 1e9 + 7;

struct segtree_bal
{
	int n;
	vector<int> tmn, tmx, p;

	segtree_bal() {}

	segtree_bal(int in)
	{
		n = in;
		tmn.resize(n * 4, 0);
		tmx.resize(n * 4, 0);
		p.resize(n * 4);
	}

	void upd_seg(int v, int tl, int tr, int l, int r, int val)
	{
		if (tr < l || r < tl)
		{
			return;
		}
		if (l <= tl && tr <= r)
		{
			p[v] += val;
			return;
		}

		int tm = (tl + tr) / 2;
		upd_seg(v * 2 + 1, tl, tm, l, r, val);
		upd_seg(v * 2 + 2, tm + 1, tr, l, r, val);
		tmn[v] = min(tmn[v * 2 + 1] + p[v * 2 + 1], tmn[v * 2 + 2] + p[v * 2 + 2]);
		tmx[v] = max(tmx[v * 2 + 1] + p[v * 2 + 1], tmx[v * 2 + 2] + p[v * 2 + 2]);
	}

	void upd(int l, int r, int val)
	{
		upd_seg(0, 0, n - 1, l, r, val);
	}

	int get_seg_mx(int v, int tl, int tr, int val)
	{
		val -= p[v];
		if (tmx[v] <= val)
		{
			return tl;
		}
		if (tmn[v] > val)
		{
			return n - 1;
		}

		int tm = (tl + tr) / 2;
		int mxl = tmx[v * 2 + 1] + p[v * 2 + 1], mxr = tmx[v * 2 + 2] + p[v * 2 + 2];
		if (mxr > val)
		{
			return get_seg_mx(v * 2 + 2, tm + 1, tr, val);
		}
		return min(get_seg_mx(v * 2 + 1, tl, tm, val), tm + 1);
	}

	int get_mx_bord(int val)
	{
		return get_seg_mx(0, 0, n - 1, val);
	}

	int get_seg_mn(int v, int tl, int tr, int val)
	{
		val -= p[v];
		if (tmn[v] >= val)
		{
			return tl;
		}
		if (tmx[v] < val)
		{
			return n - 1;
		}

		int tm = (tl + tr) / 2;
		int mnl = tmn[v * 2 + 1] + p[v * 2 + 1], mnr = tmn[v * 2 + 2] + p[v * 2 + 2];
		if (mnr < val)
		{
			return get_seg_mn(v * 2 + 2, tm + 1, tr, val);
		}
		return min(get_seg_mn(v * 2 + 1, tl, tm, val), tm + 1);
	}

	int get_mn_bord(int val)
	{
		return get_seg_mn(0, 0, n - 1, val);
	}
};

struct segtree_pm
{
	int n;
	vector<int> t;
	vector<long long> a;

	segtree_pm() {}

	segtree_pm(int in, long long val)
	{
		n = in;
		t.resize(n * 4);
		a.resize(n, val);
		build(0, 0, n - 1);
	}

	int choose(int t1, int t2)
	{
		return (a[t1] < a[t2] ? t1 : t2);
	}

	void build(int v, int tl, int tr)
	{
		if (tl == tr)
		{
			t[v] = tl;
			return;
		}

		int tm = (tl + tr) / 2;
		build(v * 2 + 1, tl, tm);
		build(v * 2 + 2, tm + 1, tr);
		t[v] = choose(t[v * 2 + 1], t[v * 2 + 2]);
	}

	void set_elem(int v, int tl, int tr, int pos, long long val)
	{
		if (tl == tr)
		{
			a[tl] = val;
			return;
		}

		int tm = (tl + tr) / 2;
		if (pos <= tm)
		{
			set_elem(v * 2 + 1, tl, tm, pos, val);
		}
		else
		{
			set_elem(v * 2 + 2, tm + 1, tr, pos, val);
		}
		t[v] = choose(t[v * 2 + 1], t[v * 2 + 2]);
	}

	void set(int pos, long long val)
	{
		set_elem(0, 0, n - 1, pos, val);
	}

	int get_min_elem(int v, int tl, int tr, int l)
	{
		if (tr < l)
		{
			return n - 1;
		}
		if (l <= tl)
		{
			return t[v];
		}

		int tm = (tl + tr) / 2;
		return choose(get_min_elem(v * 2 + 1, tl, tm, l), get_min_elem(v * 2 + 2, tm + 1, tr, l));
	}

	int get_min_idx(int l)
	{
		return get_min_elem(0, 0, n - 1, l);
	}
};

void solve()
{
	long long k, n;
	vector<long long> v;
	cin >> k >> n;
	v.resize(n);
	for (long long i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	reverse(v.begin(), v.end());

	segtree_bal sgtbal(n);
	sgtbal.upd(0, n - 1, k);
	long long bal = k;
	segtree_pm sgtpl(n, INF), sgtsb(n, INF);
	long long ans = 0;
	for (long long i = 0; i < n; i++)
	{
		if (v[i] >= 0)
		{
			bal--;
			sgtbal.upd(i, n - 1, -1);
			sgtsb.set(i, v[i]);
			ans += v[i];
			if (bal < 0)
			{
				long long border = sgtbal.get_mx_bord(k - 2);
				long long best = sgtsb.get_min_idx(border);
				sgtpl.set(best, -v[best]);
				sgtsb.set(best, INF);
				sgtbal.upd(best, n - 1, 2);
				bal += 2;
				ans -= v[best] * 2;
			}
		}
		else
		{
			bal++;
			sgtbal.upd(i, n - 1, 1);
			sgtpl.set(i, -v[i]);
			ans -= v[i];
			if (bal > k)
			{
				long long border = sgtbal.get_mn_bord(2);
				long long best = sgtpl.get_min_idx(border);
				sgtsb.set(best, v[best]);
				sgtpl.set(best, INF);
				sgtbal.upd(best, n - 1, -2);
				bal -= 2;
				ans += v[best] * 2;
			}
		}
	}
	cout << ans << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

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

	return 0;
}

/*

























*/
