#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>

typedef long long ll;
typedef double db;
typedef long double ld;

#define pb push_back
#define sz(s) int(s.size())
#define mp make_pair
#define all(s) s.begin(), s.end()

const int MAX_N = 3e3 + 10;
const int LOG = 20;
const ld EPS = 1e-7;
const ll INF = 1e18;

using namespace std;

ll x[MAX_N];
ll dp[MAX_N][MAX_N];
void solve() {
    int n, m;
    cin >> n >> m;
    ll dop = 0;
    if (n > 2) {

    }
    ll s = 0;
    for (int i = 0; i < m; i++) {
        cin >> x[i];
        s += x[i];
    }
    
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= m; j++) {
            dp[j][i] = INF;
        }
        
    }
    dp[m - 1][0] = 0;
    for (int i = m - 2; i >= 0; i--) {
        for (int j = 0; n * j <= m - i; j++) {
            if (m - i <= n * (j + 1))
                dp[i][j] = dp[i + 1][j];    
            if (m - i >= 2 * j && j != 0) 
                dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + x[i]);

        }
    }
    ll mn = INF;
    for (int j = 0; j < m; j++) {
        mn = min(mn, dp[0][j]);
    }
    cout << s - 2 * mn << endl;

    

}
int main () {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    


    
}