#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#define LOCAL

// std::mt19937 rnd(time(0));

void solve();

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifdef LOCAL
        std::freopen("input.txt", "r", stdin);
        std::freopen("output.txt", "w", stdout);
    #endif

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

void solve() {
    int n, m;
    std::cin >> n >> m;

    int rule = 1;

    std::vector <int> x(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> x[i];
        if (x[i] < 0) rule = 0;
    }

    if (n == 1) {
        long long res = 0;
        for (long long i : x) {
            res = i - res;
        }
        std::cout << res << '\n';
        return;
    }

    if (rule) {
        
    }

    std::vector <long long> prevLayer(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        std::vector <long long> nextLayer(n + 1, LLONG_MIN);
        for (int cnt = 0; cnt <= n; ++cnt) {
            if (cnt > 0 && prevLayer[cnt] != LLONG_MIN) {
                nextLayer[cnt - 1] = std::max(nextLayer[cnt - 1], prevLayer[cnt] + x[i]);
            }
            if (cnt < n && prevLayer[cnt] != LLONG_MIN) {
                nextLayer[cnt + 1] = std::max(nextLayer[cnt + 1], prevLayer[cnt] - x[i]);
            }
        }
        std::swap(prevLayer, nextLayer);
    }

    std::cout << prevLayer[0] << '\n';
}
