#include <bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int m; cin >> m;
        vector<int> a(m + 1);
        for (int i = 1; i <= m; ++i) cin >> a[i];
        // dp[len][open_plus]
        reverse(a.begin() + 1, a.end());
        int neg = 0;
        for (int i = 1; i <= m; ++i) {
            neg += (a[i] < 0);
        }
        if (neg == 0) {
            multiset<int> q;
            int ans = 0, bal = 0;
            for (int i = 1; i <= m; ++i) {
                if (bal < n) {
                    if (bal > 1) q.insert(a[i]);
                    ans += a[i];
                    bal++;
                } else {
                    int it = 1e9 + 9;
                    if (q.empty() == false) it = *q.begin();
                    if (it > a[i]) {
                        ans -= a[i]; bal--;
                    } else {
                        ans -= 2 * (*q.begin()), ans += a[i];
                        q.erase(q.begin());
                        if (bal > 1) q.insert(a[i]);
                        bal--;
                    }
                }
            }
            cout << ans << '\n';
            continue;
        }
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1e18));
        dp[0][n] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int balance = 0; balance <= n; ++balance) {
                if (balance > 0) dp[i][balance - 1] = max(dp[i][balance - 1], dp[i - 1][balance] + a[i]);
                if (balance < n) dp[i][balance + 1] = max(dp[i][balance + 1], dp[i - 1][balance] - a[i]);
            }
        }
        cout << *max_element(dp[m].begin(), dp[m].end()) << '\n';
    }
    return 0;
}
