#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'
ll solve0(int n, int m, vector<ll> x) {
	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;
	}
	return *max_element(dp1.begin(), dp1.end());
}
void solve() {
	int n, m; cin >> n >> m; vector<ll> x(m);
	for (auto& i : x) cin >> i;
	bool byl = 1;
	for (int i = 1; i < m; i++) {
		if (x[i] != x[i - 1]) exit(-1);
	}
	if (x[0] < 0) exit(-1);
	ll sum = 0;
	for (auto i : x) sum += i;
	ll ln = (m - n + 1) / 2;
	sum -= 2ll * ln * x[0];
	if (sum != solve0(n, m, x)) exit(-1);
	cout << sum << endl;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t; cin >> t;
	while (t--) solve();
	return 0;
}
