#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<long long> 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) {
            long long ans = 0, bal = 0;
            struct seg1 {
                vector<pair<int, int>> tree;
                void init(int n) {
                    tree.resize(4 * n + 1, {1e9 + 9, 1e9 + 9});
                    return;
                }
                void update(int v, int tl, int tr, int pos, int val) {
                    if (tl == tr) {
                        tree[v] = {val, tl};
                        return;
                    }
                    int tm = (tl + tr) >> 1;
                    if (pos <= tm) update(v * 2, tl, tm, pos, val);
                    else update(v * 2 + 1, tm + 1, tr, pos, val);
                    tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
                    return;
                }
                pair<int, int> get(int v, int tl, int tr, int l, int r) {
                    if (l > r) return {1e9 + 9, 1e9 + 9};
                    if (tl == tr) {
                        return tree[v];
                    }
                    int tm = (tl + tr) >> 1;
                    return min(get(v * 2, tl, tm, l, min(r, tm)), get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
                }
            };
            seg1 T;
            struct seg2 {
                struct node {
                    int mn;
                    int add;
                };
                vector<node> tree;
                void init(int n) {
                    tree.resize(4 * n + 4);
                    return;
                }
                void push(int v) {
                    if (tree[v].add == 0) return;
                    int add = tree[v].add;
                    tree[v * 2].add += add;
                    tree[v * 2 + 1].add += add;
                    tree[v * 2].mn += add;
                    tree[v * 2 + 1].mn += add;
                    tree[v].add = 0;
                    return;
                }
                int get(int v, int tl, int tr, int l, int r) {
                    if (l > r) return (int)(1e9 + 9);
                    if (tl == l && tr == r) return tree[v].mn;
                    int tm = (tl + tr) >> 1;
                    push(v);
                    return min(get(v * 2, tl, tm, l, min(r, tm)), get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
                }
                void update(int v, int tl, int tr, int l, int r, int val) {
                    if (l > r) return;
                    if (tl == l && tr == r) {
                        tree[v].add += val;
                        tree[v].mn += val;
                        return;
                    }
                    int tm = (tl + tr) >> 1;
                    push(v);
                    update(v * 2, tl, tm, l, min(r, tm), val);
                    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
                    tree[v].mn = min(tree[v * 2].mn, tree[v * 2 + 1].mn);
                    return;
                }
            };
            T.init(m + 1);
            seg2 TT;
            TT.init(m + 1);
            for (int i = 1; i <= m; ++i) {
                if (bal < n) {
                    bal++;
                    ans += a[i];
                    T.update(1, 1, m, i, a[i]);
                } else {
                    pair<int, int> mn = {1e9, 1e9};
                    /*for (int j = 1; j < i; ++j) {
                        if (c[j] == 1) {
                            c[j] = -1;
                            if (check()) mn = min(mn, pair<int, int>{a[j], j});
                            c[j] = 1;
                        }
                    }*/
                    /*cout << "!";
                    for (int i = 1; i <= m; ++i) cout << T.get(1, 1, m, i, i).first << ' ';
                    cout << endl;
                    for (int i = 1; i <= m; ++i) cout << TT.get(1, 1, m, i, i) << ' ';
                    cout << endl;*/
                    auto checker = [&](int len) {
                        int l = i - len, r = i - 1;
                       /// cout << l << ' '<< r << ' '<< TT.get(1, 1, m, l, r) << endl;
                        if (TT.get(1, 1, m, l, r) > 1) return true;
                        else return false;
                    };
                    int l = 1, r = i - 1;
                    while (true) {
                        if (l == r) break;
                        if (l + 1 == r) {
                            if (checker(r)) l++;
                            break;
                        }
                        int mid = (l + r) >> 1;
                        if (checker(mid) == true) l = mid;
                        else r = mid;
                    }
                    if (checker(l)) {
                        mn = min(mn, T.get(1, 1, m, i - l, i - 1));
                    }
                    if (mn.first > a[i]) {
                        ans -= a[i];
                        bal--;
                    } else {
                        ans -= 2 * mn.first;
                        ans += a[i];
                        T.update(1, 1, m, mn.second, 1e9 + 9);
                        T.update(1, 1, m, i, a[i]);
                        TT.update(1, 1, m, mn.second, i - 1, -2);
                        bal--;
                    }
                }
                TT.update(1, 1, m, i, 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;
}
