#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll q = 1;
    cin >> q;
    while (q--) {
        solve();
    }
}

const ll INF = 1e18;

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<ll> x(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i];
    }
    reverse(x.begin(), x.end());
    vector<map<ll, ll>> dp(m + 1);
    dp[0][0] = 0;
    ll ans = -INF;
    queue<pair<ll, ll>> bfs;
    bfs.emplace(0, 0);
    while (!empty(bfs)) {
        ll i = bfs.front().first;
        ll j = bfs.front().second;
        bfs.pop();
        if (i == m) {
            ans = max(ans, dp[i][j]);
            continue;
        }
        if (i + 1 - n <= 2 * j && 2 * j <= i + 1) {
            if (dp[i + 1].find(j) == dp[i + 1].end()) {
                bfs.emplace(i + 1, j);
                dp[i + 1][j] = dp[i][j] + x[i];
            }
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + x[i]);
        }
        if (i + 1 - n <= 2 * j + 2 && 2 * j + 2 <= i + 1 && i + 1 - n + 100 >= j) {
            if (dp[i + 1].find(j + 1) == dp[i + 1].end()) {
                bfs.emplace(i + 1, j + 1);
                dp[i + 1][j + 1] = dp[i][j] - x[i];
            }
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] - x[i]);
        }
    }
    cout << ans << '\n';
} 