#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll c = ll(1e6) + 1;

vector<ll> x;

map<vector<ll>, ll> mapa;

ll f(ll i, ll k0, ll k1) {
    if (i == x.size()) return k0 + k1;
    if (mapa.find({i, k0, k1}) != mapa.end()) return mapa[{i, k0, k1}];
    ll ans = max(f(i + 1, x[i] - k0, k1), f(i + 1, k0, x[i] - k1));
    mapa[{i, k0, k1}] = ans;
    return ans;
}

void solve() {
    mapa.clear();
    ll n, m;
    cin >> n >> m;
    x.assign(m, 0);
    for (int i = 0; i < m; i++) cin >> x[i];
    reverse(x.begin(), x.end());
//    cout << f(0, 0, 0) << " mapa\n";
    vector<vector<ll>> dp(m, vector<ll>(n + 1, -inf));
    dp[0][1] = x[0];
    for (int i = 1; i < m; i++) {
        for (int j0 = 0; j0 <= n; j0++) {
            if (j0 != 0) dp[i][j0 - 1] = max(dp[i][j0 - 1], dp[i - 1][j0] - x[i]);
            if (j0 != n) dp[i][j0 + 1] = max(dp[i][j0 + 1], dp[i - 1][j0] + x[i]);
        }
    }
    ll ans = -inf;
    for (int i = 0; i < m + 1; i++) {
        for (int j = 0; j < n + 1; j++) {
            ans = max(ans, dp[m - 1][j]);
        }
    }
    cout << ans << "\n";
}

int main() {
#ifdef KABANDJAN
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
