#define _CRT_SECURE_NO_WARNINGS


#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>


using namespace std;
using ll=long long;
const ll inf = 1e15;

int main() {
#ifdef _DEBUG
	freopen("in.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t;
	cin >> t;
	for (int trtr = 1; trtr <= t; ++trtr) {
		ll n, m;
		cin >> n >> m;
		vector<ll> x(m+1);
		ll fl = 0;
		for (int i = 1; i <= m; ++i) {
			cin >> x[m-i+1];
			if (x[m + 1 - i] != x[m]) {
				fl = 1;
			}
		}
		if (fl == 0) {
			ll h = min(n, m);
			ll sum = x[1] * h;
			ll l = m - h;
			sum -= (h % 2) * x[1];
			cout << sum << "\n";
			continue;
		}
		vector<vector<ll> > dp;
		vector<ll> ggg(n+1,-inf);
		dp.resize(m + 1, ggg);
		dp[0][0] = 0;
		for (int i = 1; i <= m; ++i) {
			for (int j = 0; j <n; ++j) {
				dp[i][j + 1] = max(dp[i][j + 1],dp[i-1][j]+x[i] );
			}
			for (int j = 1; j <= n; ++j) {
				dp[i][j - 1] = max(dp[i][j - 1], dp[i-1][j] - x[i]);
			}
		}
		ll ans = -inf;
		for (int i = 0; i <= n; ++i) {
			ans = max(ans, dp[m][i]);
		}
		cout << ans << "\n";
	}
}