#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 __int128
#define ll long long

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<ll> A(m);
    for (int i = 0; i < m; i++) {
        cin >> A[i];
    }
    vector<vector<vector<int>>> pred(n + 1, vector<vector<int>>(m, vector<int>(m, -1e18)));
    for (int k = 1; k <= n; k++){
        for (int len = 2; len <= m; len+=2){
            for (int i = 0; i <= m - len; i++){
                int j = i + len - 1;
                if (j == i + 1 and k == 1){
                    pred[k][i][j] = A[j] - A[i];
                }else{
                    pred[k][i][j] = max(pred[k][i][j], pred[k - 1][i + 1][j - 1] - A[i] + A[j]);
                    for (int r = i; r < j; r++){
                        pred[k][i][j] = max(pred[k][i][j], pred[k][i][r] + pred[k][r + 1][j]);
                    }
                }
            }
        }
    }
    vector<vector<vector<int>>> temp(n + 1, vector<vector<int>>(m, vector<int>(m, -1e18)));
    for (int l = 0; l <= n; l++){
        for (int i = 0; i < m; i++){
            for (int j = i + 1; j < m; j++){
                for (int l1 = l; l1 <= n; l1++){
                    temp[l1][i][j] = max(temp[l1][i][j], pred[l][i][j]);
                }
            }
        }
    }
    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 <= m - i; k += 2){
                for (int j1 = 0; j1 <= j; j1++) {
                    dp[i + k][j1] = max(dp[i + k][j1], dp[i][j] + temp[n - j1][i][i + k - 1]);
                }
            }
        }
    }
    cout << (ll)*max_element(dp[m].begin(), dp[m].end()) << '\n';
}

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