
#pragma GCC optimize("O3,unroll-loops,inline")

#include <bits/allocator.h>

#pragma GCC target("avx2,popcnt")

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
using ull = unsigned long long;

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

mt19937 rnd(1337);

constexpr int inf = 1e18;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    for (int &i : x)
        cin >> i;
    reverse(all(x));
    vector<pair<int, int>> dp, ndp;
    dp.push_back({0, 0});
    for (int i = 0; i < m; ++i) {
        ndp.clear();
        for (auto [j, c] : dp)
            if (j < n)
                ndp.push_back({j + 1, c + x[i]});
        for (auto [j, c] : dp)
            if (j > 0)
                ndp.push_back({j - 1, c - x[i]});
        sort(all(ndp), [&](auto a, auto b) {
            if (a.first != b.first)
                return a < b;
            return a.second > b.second;
        });
        int mx = -inf;
        dp.clear();
        for (auto j : ndp)
            if (j.second > mx) {
                mx = j.second;
                dp.push_back(j);
            }
    }
    cout << dp.back().second << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) solve();
//    cerr << fixed << setprecision(10) << clock() * 1.0 / CLOCKS_PER_SEC << '\n';
}
