#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend();

void solve();

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cout << fixed << setprecision(30);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
}

const int N = 300300;
ll shape[N], shape_sz;

struct line {
	ll off_x, off_y;
	line() = default;
	line(ll a, ll b) : off_x(a), off_y(b) {}
	ll operator[](int x) {
		if (x < off_x) {
			return -1'000'000'000'000ll * (off_x - x) + off_y;
		}
		if (x >= off_x + shape_sz) {
			return -1'000'000'000'000ll * (x - off_x - shape_sz + 1) + off_y;
		}
		return shape[x - off_x] + off_y;
	}
};

struct li_chao {
	struct node {
		line ln;
		node *l, *r;
		node(line _ln) {
			ln = _ln;
			l = nullptr;
			r = nullptr;
		}
	};
	node *root;
	size_t sz;
	li_chao(int n) {
		root = nullptr;
		sz = 1;
		while (sz < n) sz <<= 1;
	}
	void insert(line ln) {
		root = _insert(ln, 0, sz - 1, root);
	}
	node *_insert(line ln, int l, int r, node *i) {
		if (!i) {
			return new node(ln);
		}
		int m = (l + r) / 2;
		if (ln[m] > i->ln[m]) {
			swap(ln, i->ln);
		}
		if (ln[l] > i->ln[l]) {
			i->l = _insert(ln, l, m, i->l);
		} else {
			i->r = _insert(ln, m + 1, r, i->r);
		}
		return i;
	}
	ll get_max(int idx) {
		return _get_max(idx, 0, sz - 1, root);
	}
	ll _get_max(int idx, int l, int r, node *i) {
		if (!i) {
			return INT64_MIN / 2;
		}
		int m = (r + l) / 2;
		if (idx <= m) {
			return max(i->ln[idx], _get_max(idx, l, m, i->l));
		}
		return max(i->ln[idx], _get_max(idx, m + 1, r, i->r));
	}
};

struct sm_vec {
	vector<ll> left;
	vector<ll> right;
	int n;
	ll trash;
	sm_vec() = default;
	sm_vec(int _n, int bound) {
		left.resize(bound, INT64_MIN / 2);
		right.resize(bound, INT64_MIN / 2);
		n = _n;
		trash = 0;
	}
	ll &operator[](int ind) {
		if (ind < n / 2) {
			if (ind >= left.size()) return trash;
			return left[ind];
		} else {
			if (n - ind >= right.size()) return trash;
			return right[n - ind];
		}
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> x(m);
	for (int i = 0; i < m; i++) {
		cin >> x[i];
	}
	reverse(all(x));
	int sz = 1;
	while (sz < m) sz <<= 1;
	while (x.size() < sz) {
		x.push_back(0);
	}
	vector<sm_vec> dp(sz + 1);
	for (int i = 0; i <= sz; i++) {
		int mx_dg = 0, c_i = i;
		while ((1 << mx_dg) < sz && c_i % 2 == 0) {
			c_i /= 2;
			mx_dg++;
		}
		dp[i] = sm_vec(n, (1 << (mx_dg + 2)));
	}
	dp[0][0] = 0;
	for (int i = 0; i < sz; i++) {
		int mx_dg = 0, c_i = i;
		while ((1 << mx_dg) < sz && c_i % 2 == 0) {
			c_i /= 2;
			mx_dg++;
		}
		for (int j = 0; j < (1 << (mx_dg + 2)); j++) {
			if ((j + i) % 2) {
				dp[i].left[j] = INT64_MIN / 2;
			}
			if ((n - j + i) % 2) {
				dp[i].right[j] = INT64_MIN / 2;
			}
		}
		dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] - x[i]);
		dp[i + 1][n] = max(dp[i + 1][n], dp[i][n - 1] + x[i]);
		dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + x[i]);
		dp[i + 1][n - 1] = max(dp[i + 1][n - 1], dp[i][n] - x[i]);
		for (int l = 0; l <= mx_dg; l++) {
			int len = (1 << (l + 1));
			vector<ll> can;
			shape[0] = 0;
			for (int ii = i; ii < i + (1 << l); ii++) {
				can.push_back(x[ii]);
				shape[0] += x[ii];
			}
			sort(all(can));
			shape_sz = 2 * can.size() + 1;
			for (int j = 1; j < shape_sz; j++) {
				shape[j] = shape[j - 1] - can[(j - 1) / 2];
			}
			{
				reverse(shape, shape + shape_sz);
				vector<ll> cur;
				for (int j = (1 << l); j < (1 << l) + len; j++) {
					if (n - j < (1 << l)) break;
					cur.push_back(dp[i][j]);
				}
				li_chao lc(1 << (l + 2));
				for (int j = 0; j < cur.size(); j++) {
					lc.insert(line(j, cur[j]));
				}
				for (int j = 0; j < cur.size() + shape_sz - 1; j++) {
					dp[i + (1 << l)][j] = max(dp[i + (1 << l)][j], lc.get_max(j));
				}
			}
			{
				reverse(shape, shape + shape_sz);
				vector<ll> cur;
				for (int j = (1 << l); j < (1 << l) + len; j++) {
					if (n - j < (1 << l)) break;
					cur.push_back(dp[i][n - j]);
				}
				li_chao lc(1 << (l + 2));
				for (int j = 0; j < cur.size(); j++) {
					lc.insert(line(j, cur[j]));
				}
				for (int j = 0; j < cur.size() + shape_sz - 1; j++) {
					dp[i + (1 << l)][n - j] = max(dp[i + (1 << l)][n - j], lc.get_max(j));
				}
			}
		}
	}
	ll ans = INT64_MIN / 2;
	for (int i = 0; i <= n; i += 2) {
		ans = max(ans, dp[sz][i]);
	}
	cout << ans << '\n';
}
