#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
#include<random>
#include<bitset>
#include<ctime>

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2")

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using uint = unsigned int;

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
mt19937 mt(time(0));
const int N = 3e5 + 2, inf = 1e9 + 100, mod = 1e9 + 7, mod2 = 998244353, P = 257;
const ll llinf = 1e18 + 100;
//struct segtree {
//	struct node {
//		int mn, ind;
//		node() : mn(inf), ind(-1) {}
//		node operator+(node a) {
//			node ans;
//			ans.mn = min(mn, a.mn);
//			ans.ind = a.mn == ans.mn ? a.ind : ind;
//		}
//	};
//	node t[N * 2];
//	segtree() {
//		fill(t, t + N * 2, node());
//	}
//	void upd(int v, int l, int r, int i, int val) {
//		if (r - l == 1) {
//			t[v].mn = i;
//			t[v].
//		}
//	}
//};
int n, m, a[N];
bool used[N];

void solve() {
	cin >> n >> m;
	ll sum = 0;
	for (int i = 0; i < m; ++i) cin >> a[i];
	reverse(a, a + m);
	int cnt = 0;
	for (int i = 0; i < m; ++i) {
		if (a[i] >= 0) {
			used[i] = true;
			sum += a[i];
			++cnt;
		}
		else {
			used[i] = false;
			sum -= a[i];
			--cnt;
		}
		if (cnt > n) {
			int last1 = 0, s = 0;
			for (int j = 0; j <= i; ++j) {
				if (s <= 1) last1 = j;
				s += (used[j] ? 1 : -1);
			}
			int mn = inf, ind = -1;
			for (int j = last1; j <= i; ++j) {
				if (used[j] && a[j] < mn) mn = a[j], ind = j;
			}
			sum -= mn * 2;
			used[ind] = false;
			cnt -= 2;
		}
		if (cnt < 0) {
			int last1 = 0, s = 0;
			for (int j = 0; j <= i; ++j) {
				if (s >= n - 1) last1 = j;
				s += (used[j] ? 1 : -1);
			}
			int mx = -inf, ind = -1;
			for (int j = last1; j <= i; ++j) {
				if (!used[j] && a[j] > mx) mx = a[j], ind = j;
			}
			sum += mx * 2;
			used[ind] = true;
			cnt += 2;
		}
	}
	cout << sum;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tt = 1;
	cin >> tt;
	while (tt--) {
		solve();
		cout << '\n';
		cout.flush();
	}
	return 0;
}