#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("O3")
#endif

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) int((x).size())
using ld = long double;
using ll = int64_t;
using ull = uint64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;

void solve();

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

void solve() {
    int n, m;
    cin >> n >> m;
    n = min(n, 5);
    // multiset<ll> a;
    // for (int i = 0; i < n; i++) {
    //     a.insert(0);
    // }
    vector<ll> x(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i];
    }
    if (m % 2) {
        x.insert(x.begin(), 0);
        m++;
    }
    // for (ll z : x) {
    //     ll y = *a.begin();
    //     a.erase(a.begin());
    //     a.insert(z - y);
    // }
    // ll ans = 0;
    // for (ll g : a) {
    //     ans += g;
    // }
    // cout << ans << '\n';
    vector<ll> dp(n + 1);
    // vector<vector<ll>> dp(m + 1, vector<ll>(n + 1, -1e18));
    for (ll j = 0; j <= m && j <= n; j += 2) {
        dp[j] = 0;
    }
    for (int i = 0; i < m; i++) {
        vector<ll> new_dp(n + 1, -1e18);
        for (int j = 0; j <= n; j++) {
            if (j > 0) {
                new_dp[j - 1] = max(new_dp[j - 1], dp[j] + x[i]);
            }
            if (j < n) {
                new_dp[j + 1] = max(new_dp[j + 1], dp[j] - x[i]);
            }
        }
        swap(dp, new_dp);
    }
    cout << dp[0] << '\n';
}