#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 2000 + 5;

ll x[N];
ll dp[N][N];

void solve() {
    ll n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x[i];
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dp[i][j] = (ll) -1e18;
        }
    }
    dp[m + 1][n] = 0;
    for (int i = m; i >= 1; --i) {
        for (int j = 0; j <= n; ++j) {
            dp[i][j + 1] = max(dp[i][j + 1], dp[i + 1][j] - x[i]);
            if (j)dp[i][j - 1] = max(dp[i][j - 1], dp[i + 1][j] + x[i]);
        }
    }
    ll ans = 0;
    for (int i = 0; i <= n; ++i) {
        ans = max(ans, dp[1][i]);
    }
    cout << ans << '\n';
}

int main() {
    int test = 1;
    cin >> test;
    while (test--) {
        solve();
    }
}
