#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <iomanip>
using namespace std;
using ll = long long;
using ld = long double;
#define endl '\n'
void solve() {
	int n, m; cin >> n >> m; vector<ll> x(m);
	for (auto& i : x) cin >> i;
	reverse(x.begin(), x.end());
	ll sum = 0;
	for (auto i : x) sum += i;
	ll res = 0;
	for (int i = 0; i < m; i++) {
		if (i & 1) {
			res -= x[i];
		}
		else {
			res += x[i];
		}
	}
	if (n == 1) {
		cout << res << endl; return;
	}
	vector<pair<ll, ll>> dp(m + 1, { 0, 0 });
	for (int i = 0; i < m; i++) {
		dp[i + 1] = dp[i];
		if (i > 0 && (dp[i + 1].first > dp[i - 1].first + x[i] || (dp[i + 1].first == dp[i - 1].first + x[i] && dp[i + 1].second < dp[i - 1].second + 1))) {
			dp[i + 1] = dp[i - 1]; dp[i + 1].first += x[i]; dp[i + 1].second++;
		}
	}
	int ln = max(0, (m - n + 1) / 2);
	if (dp[m].second >= ln) {
		cout << sum - 2 * dp[m].first << endl; return;
	}
	vector<ll> dp1(n + 1, -1e18); dp1[0] = 0;
	for (int i = 0; i < m; i++) {
		vector<ll> dp2(n + 1, -1e18);
		for (int j = 0; j <= n; j++) {
			if (j > 0) dp2[j - 1] = max(dp2[j - 1], dp1[j] - x[i]);
			if (j < n) dp2[j + 1] = max(dp2[j + 1], dp1[j] + x[i]);
		}
		dp1 = dp2;
	}
	cout << *max_element(dp1.begin(), dp1.end()) << endl;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t; cin >> t;
	while (t--) solve();
	return 0;
}
