#include "bits/stdc++.h"
#pragma GCC optimize("unroll-loops", "Ofast")
using namespace std;
#define ll long long
const int inf = 2e9;
const ll INF = 2e18;

//#define int ll
#include "ext/pb_ds/assoc_container.hpp"
using namespace __gnu_pbds;
typedef tree<int, null_type, std::less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

random_device dev;
mt19937 rnd(dev());

struct fenv {
    vector<ll> t;

    fenv(int n) {
        t.assign(n, 0);
    }

    void add (int ind, ll x) {
        for (; ind < t.size(); ind = (ind | (ind + 1)))
            t[ind] += x;
    }

    ll get (int ind) {
        ll res = 0;
        for (; ind >= 0; ind = (ind & (ind + 1)) - 1)
            res += t[ind];
        return res;
    }
};

template<typename T1, typename T2>
istream& operator >> (istream &in, pair<T1, T2> &a) {
    in >> a.first >> a.second;
    return in;
}

template<typename T1, typename T2>
ostream& operator << (ostream &out, pair<T1, T2> &a) {
    out << a.first << " " << a.second;
    return out;
}

template<typename T>
istream& operator >> (istream &in, vector<T> &a) {
    for (int i = 0; i < a.size(); i++)
        in >> a[i];
    return in;
}

template<typename T>
ostream& operator << (ostream &out, vector<T> &a) {
    for (auto &i: a)
        cout << i << " ";
    return out;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<ll> a(m);
        cin >> a;

        vector<ll> dp(n + 1, -INF);
        dp[n] = 0;
        for (int i = m - 1; i >= 0; i--) {
            auto dp_ = dp;
            for (int k = 0; k <= n; k++) {
                ll left = -INF;
                if (k > 0)
                    left = dp_[k - 1];
                ll right = -INF;
                if (k < n && dp_[k + 1] != INF)
                    right = dp_[k + 1] + a[i];
                dp[k] = max(left, right);
            }
        }
        ll sum = 0;
        for (int i = 0; i < m; i++)
            sum += a[i];
        ll mx = -INF;
        for (int i = 0; i <= n; i++)
            mx = max(mx, dp[i]);
        ll res = mx * 2 - sum;
        cout << res << "\n";
    }
}
