#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define mem(x, y) memset(x, y, sizeof x)
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define int ll

const int maxn = 2010, INF = 1e18;
int a[maxn], dp[maxn][maxn];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int TC;
	cin >> TC;
	while (TC--) {
		int k, n;
		cin >> k >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		reverse(a + 1, a + n + 1);
		
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= k; j++) {
				dp[i][j] = -INF;
			}
		}
		
		int ans = -INF;
		
		dp[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= k; j++) {
				// +a[i]
				if (j > 0 && dp[i - 1][j - 1] != -INF) dp[i][j] = dp[i - 1][j - 1] + a[i];
				
				// -a[i]
				if (j < k && dp[i - 1][j + 1] != -INF) dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] - a[i]);
				
				//cout << i << ' ' << j << ' ' << dp[i][j] << endl;
				if (i == n) ans = max(ans, dp[i][j]);
			}
		}
		
		cout << ans << '\n';
	}
	
	return 0;
}
