#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long
using namespace std;
const int INF = 2e18;

void maxeq(int &x, int y) {
    if (y > x) x = y;
}

void solve() {
    int n, m;
    cin >> n >> m;
    n = min(n, 500ll);
    vector<int> dp(n + 1, -INF);
    dp[n] = 0;
    vector<int> Q(m);
    for (int &x: Q) cin >> x;
    reverse(Q.begin(), Q.end());
    for (int x: Q) {
        vector<int> new_dp(n + 1, -INF);
        for (int cnt1 = 0; cnt1 <= n; cnt1++) {
            int cnt2 = n - cnt1;
            int s = dp[cnt1];
            if (s == -INF) continue;
            if (cnt1) {
                maxeq(new_dp[cnt1 - 1], s + x);
            }
            if (cnt2) {
                maxeq(new_dp[cnt1 + 1], s - x);
            }
        }
        dp = new_dp;
    }
    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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