#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int INF = int(-1e9) * int(4e5);
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> dp(n + 1, 0);
    dp[n] = 0;
    multiset<int> s;
    vector<int> x(m);
    bool ff = true;
    int ansans = 0;
    for (int i = 0; i < m; i++) {
        cin >> x[i];
        if (n == 1) {
            if ((m - i) % 2 == 1) {
                ansans += x[i];
            }
            else {
                ansans -= x[i];
            }
        }
        if (x[i] < 0) {
            ff = false;
        }
    }
    if (n == 1) {
        cout << ansans << '\n';
        return;
    }
    for (int j = m - 1; j >= 0; j--) {
        vector<int> dp2(n + 1, INF);
        for (int i = 0; i < n; i++) {
            dp2[i] = max(dp2[i], dp[i + 1] + x[j]);
        }
        for (int i = 1; i <= n; i++) {
            dp2[i] = max(dp2[i], dp[i - 1] - x[j]);
        }
        dp = dp2;
    }
    int ans = INF;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
}
int32_t main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
