#include <bits/stdc++.h>
#define int long long

const int inf = 1e17;

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int& i : a) cin >> i;
    int ans = -inf;
    // for (int k = 1; k <= n; k++) {
    for (int k = n; k <= n; k++) {
            if (k >= m) {
            int sum = 0;
            for (int i : a) sum += i;
            ans = max(ans, sum);
            continue;
        }
        vector<vector<int>> dp(m, vector<int>(k + 1, -inf));
        vector<int> firstk;
        for (int i = 0; i < k; i++) firstk.push_back(a[i]);
        sort(firstk.begin(), firstk.end());
        vector<int> pref(k), suff(k);
        pref[0] = firstk[0];
        for (int i = 1; i < k; i++) {
            pref[i] = pref[i - 1] + firstk[i];
        }
        suff[k - 1] = firstk[k - 1];
        for (int i = k - 2; i >= 0; i--) {
            suff[i] = suff[i + 1] + firstk[i];
        }
        dp[k - 1][k] = pref[k - 1];
        dp[k - 1][0] = -pref[k - 1];
        for (int i = 1; i < k; i++) {
            dp[k - 1][i] = suff[k - i] - pref[k - i - 1];
        }
        for (int i = k; i < m; i++) {
            for (int j = 0; j <= k; j++) {
                if (j - 1 >= 0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i]);
                    // cout << i << " " << j << ": " << "+ " << dp[i][j] << "\n";
                }
                if (j + 1 <= k) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] - a[i]);
                    // cout << i << " " << j << ": " << "- " << dp[i][j] << "\n";
                }
                // cout << i << " " << j << ": " << dp[i][j] << "\n";
            }
        }
        ans = max(ans, dp[m - 1][k]);
    }
    cout << ans << "\n";
}

signed main() {
    int t;
    cin >> t;
    while (t--) solve();
}