#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

typedef long long ll;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    for (int &i : x) {
        cin >> i;
    }
    int check_st1 = 1;
    bool st1 = true;
    for (int i : x) {
        if (check_st1 == 1) {
            check_st1 = i;
        }
        st1 &= (check_st1 == i);
    }
    st1 &= (check_st1 <= 0);
    if (st1) {
        cout << (m % 2) * check_st1 << '\n';
        return;
    }
    reverse(x.begin(), x.end());
    vector<vector<ll>> dp(m + 1, vector<ll> (n + 1, 0));
    vector<vector<bool>> can(m + 1, vector<bool> (n + 1, false));
    can[0][n] = true;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (!can[i][j]) {
                continue;
            }
            if (j < n) {
                if (!can[i + 1][j + 1]) {
                    dp[i + 1][j + 1] = dp[i][j] - x[i];
                }
                can[i + 1][j + 1] = true;
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] - x[i]);
            }
            if (j > 0) {
                if (!can[i + 1][j - 1]) {
                    dp[i + 1][j - 1] = dp[i][j] + x[i];
                }
                can[i + 1][j - 1] = true;
                dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j] + x[i]);
                //cout << "smile" << ' ' << dp[i][j] + x[i] << endl;
            }
        }
    }
    /*for (auto &i : dp) {
        for (auto &j : i) {
            cout << j << ' ';
        }
        cout << '\n';
    }*/
    ll ans = 0;
    bool find = false;
    for (int i = 0; i <= n; ++i) {
        if (can[m][i] && (!find || ans < dp[m][i])) {
            find = true;
            ans = dp[m][i];
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
