#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <assert.h>
using namespace std;

#define int long long
#define ll long long
#define vi vector<int>
#define pi pair<int, int>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define vpi vector<pi>
#define vvi vector<vi>

bool cmp(int a, int b) {
	return abs(a) < abs(b);
}

signed main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		vi vec(m);
		for (int i = 0; i < m; i++) {
			cin >> vec[i];
		}
		reverse(all(vec));
		vvi dp(m + 1, vi(n + 1, -1e18));
		dp[0][n] = 0;
		for (int i = 0; i < m; i++) {
			for (int p = 0; p <= n; p++) {
				if (p != n) {
					dp[i + 1][p + 1] = max(dp[i + 1][p + 1], dp[i][p] - vec[i]);
				}
				if (p) {
					dp[i + 1][p - 1] = max(dp[i + 1][p - 1], dp[i][p] + vec[i]);
				}
			}
			int id = max_element(all(dp[i + 1])) - dp[i + 1].begin();
			for (int j = (id & 1); j < id; j += 2) {
				if (dp[i + 1][j] > dp[i + 1][j + 2]) {
					assert(false);
				}
			}
			for (int j = id + 2; j < n; j += 2) {
				if (dp[i + 1][j] > dp[i + 1][j - 2]) {
					assert(false);
				}
			}
		}
		cout << *max_element(all(dp[m])) << '\n';
	}
}