#include <iostream>

#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    long long inf = 100000000000000000;
    int t;
    cin >> t;
    for (int w = 0; w < t; w++) {
        int n, m;
        cin >> n >> m;
        vector <long long> xx(m);
        for (int i = 0; i < m; i++) {
            cin >> xx[m - i - 1];
        }
        if (n * m > 4000000) {
            if (m % 2) {
                cout << xx[0] << '\n';
            } else {
                cout << 0 << '\n';
            }
        } else {
            vector <vector <long long>> dp(m + 1, vector <long long>(n + 1, -inf));
            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] = dp[i][j - 1] - xx[i];
                    }
                    if (j != n) {
                        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + 1] + xx[i]);
                    }
                }
            }
            long long ans = -inf;
            for (int j = 0; j <= n; j++) {
                ans = max(ans, dp[m][j]);
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

