#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <iomanip>
#include <queue>
#include <unordered_map>
using namespace std;
using ll = long long;
const ll INF = 1e18;
void solve() {
	ll n, m;
	cin >> n >> m;
	vector<ll> v(m);
	ll sum = 0;
	bool same = true;
	set<ll> se;
	for (ll i = 0; i < m; ++i)
		cin >> v[i], se.insert(v[i]);
	if (se.size() == 1) {
		ll ans = v[0] * min(n - 1, m);
		if ((m - (n - 1)) % 2 == 1)
			ans += v[0];
		cout << ans << endl;
		return;
	}
	vector<vector<ll>> dp(m + 1, vector<ll>(n + 2, INF));
	dp[m][0] = 0;
	for (ll i = m - 1; i >= 0; --i) {
		for (ll j = 0; j <= n; ++j) {
			if (j > 0 && dp[i + 1][j + 1] != INF && dp[i + 1][j - 1] != INF)
				dp[i][j] = max(v[i] + dp[i + 1][j - 1], -v[i] + dp[i + 1][j + 1]);
			else if (dp[i + 1][j + 1] != INF)
				dp[i][j] = -v[i] + dp[i + 1][j + 1];
			else if (j > 0 && dp[i + 1][j - 1] != INF)
				dp[i][j] = v[i] + dp[i + 1][j - 1];
		}
	}
	ll ans = -INF;
	for (ll i = 0; i <= n; ++i)
		if(dp[0][i] != INF)
			ans = max(ans, dp[0][i]);
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll t = 1;
	cin >> t;
	while (t--)
		solve();
}