#include <bits/stdc++.h>

#define int long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using namespace std;

const int inf = 1e18;

bool ckmax(int &a, int b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

void solve_case() {
    int n, m; cin >> n >> m;
    vector<int> x(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i];
    }
    int ans = -inf;
    for (int cnt_odd = 0; cnt_odd <= n; cnt_odd++) {
        // (add_even, sub_even, add_odd, sub_odd)
        vector dp(n + 1, vector(n + 1, vector(n + 1, vector<int>(n + 1, -inf))));
        dp[cnt_odd][n - cnt_odd][0][0] = 0;
        for (int i = 0; i < m; i++) {
            vector dq(n + 1, vector(n + 1, vector(n + 1, vector<int>(n + 1, -inf))));
            for (int add_even = 0; add_even <= n; add_even++) {
                for (int sub_even = 0; sub_even <= n; sub_even++) {
                    for (int add_odd = 0; add_odd <= n; add_odd++) {
                        for (int sub_odd = 0; sub_odd <= n; sub_odd++) {
                            int cur = dp[add_even][sub_even][add_odd][sub_odd];
                            if (add_even > 0 && sub_odd + 1 <= n) {
                                ckmax(dq[add_even - 1][sub_even][add_odd][sub_odd + 1], cur + x[i]);
                            }
                            if (sub_even > 0 && add_odd + 1 <= n) {
                                ckmax(dq[add_even][sub_even - 1][add_odd + 1][sub_odd], cur - x[i]);
                            }
                            if (sub_even + 1 <= n && add_odd > 0) {
                                ckmax(dq[add_even][sub_even + 1][add_odd - 1][sub_odd], cur + x[i]);
                            }
                            if (add_even + 1 <= n && sub_odd > 0) {
                                ckmax(dq[add_even + 1][sub_even][add_odd][sub_odd - 1], cur - x[i]);
                            }
                        }
                    }
                }
            }
            dp.swap(dq);
        }
        for (int add_even = 0; add_even <= n; add_even++) {
            for (int sub_even = 0; sub_even <= n; sub_even++) {
                ans = max(ans, dp[add_even][sub_even][0][cnt_odd]);
            }
        }
    }
    cout << ans << '\n';
}

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