#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define ve vector
#define pb push_back
#define all(a) a.begin(), a.end()
#define first f
#define second s
using ld = long double;
#define int ll
mt19937 rnd(321932);

template<class A>
istream &operator>>(istream &in, ve<A> &a) {
    for (auto &x: a)
        in >> x;
    return in;
}

template<class A>
ostream &operator<<(ostream &out, ve<A> a) {
    for (auto &x: a)
        out << x << ' ';
    return out << '\n';
}

void sol() {
    int n, m;
    cin >> n >> m;
    ve<int> x(m);
    cin >> x;
    reverse(all(x));
    // dp[j] --- max res if we used j bad x
    ve<int> dp(m + 1, -1e18);
    dp[0] = 0;
    for (int cnt = 1; cnt <= m; ++cnt) {
        for (int i = cnt/2 + 1; cnt + n >= 2 * i && i <= cnt; ++i) {
            dp[i] = max(dp[i], dp[i-1] + x[cnt-1]);
        }
    }
    int sum = 0;
    for (auto &c : x)
        sum += c;
    cout << 2 * (*max_element(all(dp))) - sum << '\n';
}

int32_t main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
        sol();
}
