//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <iomanip>
#include <numeric>
#include <algorithm>
#include <random>
using ll = long long;
#define int ll
#define all(a) a.begin(), a.end()

using namespace std;
//using namespace __gnu_pbds;

//using odered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rnd(0);



void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	reverse(all(a));
	vector<int> dp(n + 1, -1e18);
	dp[n] = 0;
	for (int i = 0; i < m; i++) {
		vector<int> dp1(n + 1, -1e18);
		dp1[0] = dp[1] + a[i];
		dp1[n] = dp[n - 1] - a[i];

		int j = 0;
		for (int w = 20; w >= 0; w--) {
			int j1 = j + (1 << w);
			if (j1 < n && (dp[j1 + 1] + a[i] > dp[j1 - 1] - a[i])) {
				j = j1;
			}
		}
		for (int cp = 1; cp <= j; cp++) {
			dp1[cp] = dp[cp + 1] + a[i];
		}
		for (int cp = j+1; cp < n; cp++) {
			dp1[cp] = dp[cp - 1] - a[i];
		}
		dp = dp1;
	}
	int ans = -1e18;
	for (int i = 0; i <= n; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL
	auto f1 = freopen("input.txt", "r", stdin);
	auto f2 = freopen("output.txt", "w", stdout);
#endif

	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}