#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
//#include <cmath>
//#include <numeric>

//#pragma GCC optimize("O3, unroll-loops")
//#pragma GCC target("avx2, avx, lzcnt, popcnt, bmi, bmi2")

using namespace std;

#define int long long

int get(vector<int>& pref, int l, int r) {
    if (r < l) {
        return 0;
    }
    if (l == 0) {
        return pref[r];
    }
    return pref[r] - pref[l - 1];
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> A(m);
    for (int i = 0; i < m; i++) {
        cin >> A[i];
    }
    vector<int> pref(m);
    pref[0] = A[0];
    for (int i = 1; i < m; i++) {
        pref[i] = pref[i - 1] + A[i];
    }
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1e18));
    dp[0][n] = 0;
    for (int i = 0; i < m; i++){
        for (int j = 0; j <= n; j++){
            if (j != 0){
                dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j] + A[i]);
            }
            for (int k = 2; k <= min(m - i, 2 * n); k+= 2){
                dp[i + k][min(j, n - k / 2)] = max(dp[i + k][min(j, n - k / 2)], dp[i][j] - get(pref, i, i + k / 2 - 1) + get(pref, i + k / 2, i + k - 1));
            }
        }
    }
    cout << *max_element(dp[m].begin(), dp[m].end()) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
