#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int N = 2010;

int n, m, a[N], dp[N][N];

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) cin >> a[i];

    for(int i = 0; i <= m; ++i) for(int j = 0; j <= n; ++j) dp[i][j] = -INF;
    dp[m][n] = 0;
    for(int i = m; i >= 1; --i) {
        for(int was = 0; was <= n; ++was) {
            if(dp[i][was] == -INF) continue;
            if(was > 0) dp[i - 1][was - 1] = max(dp[i - 1][was - 1], dp[i][was] + a[i]);
            if(was < n) dp[i - 1][was + 1] = max(dp[i - 1][was + 1], dp[i][was] - a[i]);
        }
    }

    cout << *max_element(dp[0], dp[0] + n + 1) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto start = clock();
#endif
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
#ifdef LOCAL
    auto end = clock();
    cerr << "TIME: " << (end - start) << "ms" << '\n';
#endif
}