// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("inline")
// #pragma GCC optimize("unroll-loops")
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
// using namespace __gnu_pbds;
using namespace std;
using ll = long long;
// using ordered_map = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
// using hash_map = gp_hash_table<int, int>;
#define watch(x) cout << #x << ": " << x << '\n';
#define watch_arr(arr) cout << #arr << ": "; \
for (int i = 0; i < (int)arr.size(); ++i) { \
    cout << arr[i] << ' '; \
} \
cout << '\n';
#define all(arr) arr.begin(), arr.end()

random_device rd;
mt19937 rnd(rd());

const ll INF = 1e18;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n, m;
        cin >> n >> m;
        vector<ll> arr(m);
        for (auto& el : arr) {
            cin >> el;
        }
        reverse(all(arr));

        
        ll ans = -INF, l = -2e9, r = 2e9;
        while (r - l > 1) {
            ll k = 0, buf = 0, s = 0;
            ll mid = (l + r) / 2;
            bool check = true;
            for (int i = 0; i < m; ++i) {
                if (k == 0 || arr[i] > mid || (m - i <= n - k && arr[i] >= 0)) {
                    s += arr[i];
                    ++k;
                } else if (arr[i] == mid) {
                    s += arr[i];
                    ++k, ++buf;
                } else {
                    s -= arr[i];
                    --k;
                }
                if (k > n) {
                    if (buf) {
                        s -= 2 * mid;
                        --k, --buf;
                    } else {
                        check = false;
                        break;
                    }
                }
            }
            if (check) {
                ans = max(ans, s);
                r = mid;
            } else {
                l = mid;
            }
        }
        
        cout << ans << ' ';
    }

    return 0;
}
