#define _CRT_SECURE_NO_WARNINGS
#ifndef _DEBUG
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <unordered_set>
#include <map>
#include <deque>
#include <queue>
#include <unordered_map>
#include <iomanip>
using namespace std;
#define int long long
using ll = long long;
using ld = long double;
using str = string;
using pll = pair<ll, ll>;
auto sd = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
void sol1() {
	ll n, m;
	cin >> n >> m;
	vector<ll> a(n);
	vector<ll> x(m);
	set<ll> w;
	for (int i = 0; i < m; i++) {
		cin >> x[i];
		w.insert(x[i]);
	}
	if (w.size() == 1) {
		if (m <= n) {
			if (x[0] < 0) {
				if (m % 2 == 0) {
					cout << 0 << endl;
				}
				else {
					cout << x[0] << endl;
				}
			}
			else {
				cout << x[0] * m << endl;
			}
		}
		else {
			if (x[0] < 0) {
				if (m % 2 == 0) {
					cout << 0 << endl;
				}
				else cout << x[0] << endl;
			}
			else {
				m -= n;
				if (m % 2 == 0) {
					cout << x[0] * n << endl;
				}
				else {
					cout << x[0] * (n - 1) << endl;
				}
			}
		}
	}
	else {
		ll mx_sum = -1e18;
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, mx_sum));
		dp[m][n] = 0;
		for (int j = m - 1; j >= 0; j--) {
			for (int i = n; i >= 0; i--) {
				if (i - 1 >= 0) dp[j][i - 1] = max(dp[j][i - 1], dp[j + 1][i] + x[j]);
				if (i + 1 <= n) dp[j][i + 1] = max(dp[j][i + 1], dp[j + 1][i] - x[j]);
			}
		}
		for (int j = n; j >= 0; j--) {
			mx_sum = max(mx_sum, dp[0][j]);
		}
		cout << mx_sum << endl;
	}
	
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
#ifdef _DEBUG
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ll t1 = 1;
	cin >> t1;
	for (int o_ = 0; o_ < t1; o_++) sol1();
}

