#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long
void solve() {

    int k;
    cin >> k;
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &i: a) cin >> i;
    vector<int> left(k + 1);
    vector<bool> ok(k + 1);
    ok[k] = true;
    for (int i = 0; i < n; ++i) {
        vector<int> nleft(k + 1);
        vector<bool> nok(k + 1);
        if (k >= 1 && ok[1]) {
            nleft[0] = left[1] + a[i];
            nok[0] = true;
        }
        if (k >= 1 && ok[k - 1]) {
            nleft[k] = left[k - 1] - a[i];
            nok[k] = true;
        }
        for (int l = 1; l < k; ++l) {
            if (ok[l - 1] && ok[l + 1]) {
                nleft[l] = max(left[l - 1] - a[i], left[l + 1] + a[i]);
                nok[l] = true;
            } else if (ok[l - 1]) {
                nleft[l] = left[l - 1] - a[i];
                nok[l] = true;
            } else if (ok[l + 1]) {
                nleft[l] = left[l + 1] + a[i];
                nok[l] = true;
            }
        }
        swap(left, nleft);
        swap(ok, nok);
    }
    int ans = 0;
    for (int i: left) { ans = max(ans, i); }
    cout << ans << '\n';
}
signed main() {
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}
