#ifdef _DEBUG
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <limits>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <chrono>
#include <random>
#include <assert.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using ld = long double;
using pii = pair<int, int>;
using pli = pair<long long, int>;
using pil = pair<int, long long>;
using pll = pair<long long, long long>;
template <typename T>
using uset = unordered_set<T>;
template <typename T1, typename T2>
using umap = unordered_map<T1, T2>;

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

const ll inf = 3e18;

void smax(ll& a, ll b) {
	a = max(a, b);
}

inline void solve() {
	int n, m;
	cin >> n >> m;
	vector<ll> x(m);
	for (int i = 0; i < m; i++)
		cin >> x[i];
	ll ans = -inf;
	for (int c1 = 0; c1 <= n; c1++) {
		int c0 = n - c1;
		vector<vector<ll>> dp(c1 + 1, vector<ll>(c0 + 1, -inf));
		dp[0][c0] = 0;
		auto tmp = dp;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j <= c1; j++)
				for (int k = 0; k <= c0; k++)
					tmp[j][k] = -inf;
			for (int p1 = 0; p1 <= c1; p1++)
				for (int p0 = 0; p0 <= c0; p0++) {
					if (p1 < c1)
						smax(tmp[p1 + 1][p0], dp[p1][p0] + x[i]);
					if (p1 > 0)
						smax(tmp[p1 - 1][p0], dp[p1][p0] - x[i]);
					if (p0 < c0)
						smax(tmp[p1][p0 + 1], dp[p1][p0] + x[i]);
					if (p0 > 0)
						smax(tmp[p1][p0 - 1], dp[p1][p0] - x[i]);
				}
			for (int j = 0; j <= c1; j++)
				for (int k = 0; k <= c0; k++)
					dp[j][k] = tmp[j][k];
		}
		ans = max(ans, dp[c1][c0]);
	}
	cout << ans << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#ifdef _DEBUG
	freopen("01.dat", "r", stdin);
#endif
	int tt = 1;
	cin >> tt;
	for (int test_id = 1; test_id <= tt; test_id++) {
#ifdef _DEBUG
		cout << "TESTCASE# " << test_id << '\n';
#endif
		solve();
	}
	return 0;
}
