#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
#include <unordered_set>

using namespace std;

using ll = long long;

const ll INF = 3e18;

struct node {
	ll sz;
	ll sum;
	ll maxrNc;
	ll maxrCh;
	ll maxl;
	ll maxNc;
	ll maxCh;
};

node merge(node a, node b) {
	if (a.sz < 0) return b;
	if (b.sz < 0) return a;
	node n;
	n.sz = a.sz + b.sz;
	n.sum = a.sum + b.sum;
	n.maxrNc = max(b.maxrNc, b.sum + a.maxrNc);
	n.maxrCh = max(b.maxrCh, b.sum + a.maxrCh);
	n.maxl = max(a.maxl, a.sum + b.maxl);
	n.maxNc = max(max(a.maxNc, b.maxNc), a.maxrNc + b.maxl);
	n.maxCh = max(max(a.maxCh, b.maxCh), a.maxrCh + b.maxl);
	return n;
}

struct segmentTree {
	vector<node> tree;

	void gen(int i, int l, int x) {
		tree[i].sz = 1;
		tree[i].sum = x;
		tree[i].maxl = max(0, x);
		if (l % 2) {
			tree[i].maxCh = -INF;
			tree[i].maxrCh = 0;
			tree[i].maxNc = x;
			tree[i].maxrNc = x;
		}
		else {
			tree[i].maxCh = x;
			tree[i].maxrCh = x;
			tree[i].maxNc = -INF;
			tree[i].maxrNc = 0;
		}
	}

	void build(int i, int l, int r, int x) {
		if (r - l == 1) {
			gen(i, l, x);
			return;
		}
		ll m = (l + r) / 2;
		build(i * 2 + 1, l, m, x);
		build(i * 2 + 2, m, r, x);
		tree[i] = merge(tree[i * 2 + 1], tree[i * 2 + 2]);
	}

	segmentTree(int n, int def) {
		tree.resize(n * 4);
		build(0, 0, n, def);
	}

	void set(int i, int l, int r, int id, int x) {
		if (r - l == 1) {
			gen(i, l, x);
			return;
		}
		int m = (l + r) / 2;
		if (id < m) set(i * 2 + 1, l, m, id, x);
		else set(i * 2 + 2, m, r, id, x);
		tree[i] = merge(tree[i * 2 + 1], tree[i * 2 + 2]);
	}

	node get(int i, int l, int r, int ql, int qr) {
		if (l >= ql && r <= qr) return tree[i];
		if (l >= qr || r <= ql) {
			node n;
			n.sz = -1;
			return n;
		}
		ll m = (l + r) / 2;
		return merge(get(i * 2 + 1, l, m, ql, qr), get(i * 2 + 2, m, r, ql, qr));
	}
};

ll check(segmentTree& znak, int x, int n) {
	znak.set(0, 0, n, x, 1);
	auto nd = znak.get(0, 0, n, 0, n);
	ll mx = max(nd.maxCh, nd.maxNc + 1);
	return mx;
}

ll check2(segmentTree& znak, int x, int n, bool nc) {
	znak.set(0, 0, n, x, 1);
	auto nd = znak.get(0, 0, n, 0, n);
	ll mx = max(nd.maxCh + (!nc), nd.maxNc + nc);
	return mx;
}

void solve() {
	ll n, m; cin >> n >> m;
	vector<ll> vec(m);
	for (int i = 0; i < m; i++) cin >> vec[i];
	reverse(vec.begin(), vec.end());
	segmentTree znak(m, -1);
	segmentTree znak2(m, -1);
	vector<ll> rznak(m, 0);
	vector<pair<ll, ll>> vp;
	for (int i = 0; i < m; i++) vp.push_back({ abs(vec[i]), i });
	sort(vp.rbegin(), vp.rend());
	for (auto p : vp) {
		if (vec[p.second] > 0) {
			ll c = check(znak, p.second, m);
			if (c > n) znak.set(0, 0, m, p.second, -1);
			else rznak[p.second] = 1;
		}
		else {
			ll c = check2(znak2, p.second, m, false);
			if (c > n) znak2.set(0, 0, m, p.second, -1);
			else rznak[p.second] = -1;
		}
	}
	ll ans = 0;
	ll cur = 0;
	for (int i = 0; i < m; i++) {
		if (rznak[i] == 1 || cur == 0) {
			ans += vec[i];
			cur++;
		}
		else {
			ans -= vec[i];
			cur--;
		}
	}
	cout << ans << endl;
}

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

	ll t; cin >> t;
	while (t--) {
		solve();
	}
}