#include <bits/extc++.h>
using namespace std;
#define int long long
mt19937 rnd(time(0));
const int MAX_N = 5e5 + 23, MAX_TREE_SIZE = (1 << 21);
int x[MAX_N];
int tree[MAX_TREE_SIZE], p[MAX_TREE_SIZE];
void push(int m){
    int l_s = 2 * m + 1, r_s = 2 * m + 2;
    tree[l_s] += p[m];
    tree[r_s] += p[m];
    p[l_s] += p[m];
    p[r_s] += p[m];
    p[m] = 0;
}
void update(int l_b, int r_b, int l, int r, int m, int val){
    if(l_b == l && r_b == r){
        tree[m] += val;
        p[m] += val;
        return;
    }
    push(m);
    int m_b = (l_b + r_b) / 2, l_s = 2 * m + 1, r_s = 2 * m + 2;
    if(l < m_b){
        update(l_b, m_b, l, min(m_b, r), l_s, val);
    }
    if(r > m_b){
        update(m_b, r_b, max(l, m_b), r, r_s, val);
    }
    tree[m] = min(tree[l_s], tree[r_s]);
    //cout << l_b << " " << r_b << " " << tree[l_s] << " " << tree[r_s] << "\n";
}
int get(int l_b, int r_b, int l, int r, int m){
    if(l_b == l && r_b == r){
        return tree[m];
    }
    push(m);
    int m_b = (l_b + r_b) / 2, l_s = 2 * m + 1, r_s = 2 * m + 2;
    int mn = 1e18;
    if(l < m_b){
       mn = min(mn, get(l_b, m_b, l, min(m_b, r), l_s));
    }
    if(r > m_b){
        mn = min(mn, get(m_b, r_b, max(l, m_b), r, r_s));
    }
    return mn;
}
void solve(){
    int n, m;
    cin >> n >> m;
    int ans = 0;
    int ca = n;
    for(int i = 0; i < m; i++){
        cin >> x[i];
    }
    reverse(x, x + m);
    set<pair<int, int>> st;
    fill(tree, tree + 4 * (m + 5), 0);
    fill(p, p + 4 * (m + 5), 0);
    for(int i = 0; i < m; i++){
        //cout << i << " "<< (i + 1) / 2  << "\n";
        update(0, MAX_N, i, i + 1, 0, (i + 1) / 2);
    }
    for(int i = 0; i < m; i++){
        st.insert({x[i], i});
        ans += x[i];
        ca--;
        while(ca < 0){
            auto el = st.begin()->first, pos = st.begin()->second;
            st.erase(st.begin());
            //cout << el << " " << pos << " " << get(0, MAX_N, pos, m, 0) << "\n";
            if(get(0, MAX_N, pos, m, 0) == 0){
                continue;
            }
            update(0, MAX_N, pos, m, 0, -1);
            ca += 2;
            ans -= 2 * el;
        }
    }
    while(st.begin()->first < 0){
        auto el = st.begin()->first, pos = st.begin()->second;
        st.erase(st.begin());
        if(get(0, MAX_N, pos, m, 0) == 0){
            continue;
        }
        //cout << el << " " << pos << " " << get(0, MAX_N, pos, m, 0) << "\n";
        update(0, MAX_N, pos, m, 0, -1);
        ca += 2;
        ans -= 2 * el;
    }
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tim = clock();
    int tt =  1;
    cin >> tt;
    while(tt--){
        solve();
    }
    //cout << (long double)(clock() - tim) / CLOCKS_PER_SEC << "\n";
}
