#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = 4e14;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> m >> n;

        vector<ll> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, -INF));
        int fp = n / m % 2;
        if (fp == 0)
            fp = n % m % 2;
        else
            fp = (m - n % m) % 2;
        for (int j = fp; j <= min(n, m); j += 2)
            dp[0][j] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = (fp + i) % 2; j <= m; j += 2) {
                if (j > 0)
                    dp[i][j] = dp[i - 1][j - 1] - a[i - 1];
                if (j < m)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] + a[i - 1]);
            }
        }

        cout << dp[n][0] << '\n';
    }
}