#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll t,n,m,i,a[300002],j,ans,cnt,s[1200002],f[1200002],si[1200002];
set<pair<ll,ll>> stv,sti;
void build(ll v, ll l, ll r){
        s[v]=0;
        f[v]=0;
    if(l==r){
        return;
    }
    ll m=(l+r)/2;
    build(2*v,l,m);
    build(2*v+1,m+1,r);
}
void push(ll v){
    f[2*v]+=f[v];
    f[2*v+1]+=f[v];
    s[v]+=f[v];
    f[v]=0;
}
void upd(ll v, ll l, ll r, ll a, ll b, ll x){
    if(l==a && r==b){
        f[v]+=x;
        return;
    }
    ll m=(l+r)/2;
    push(v);
    if(b<=m){
        upd(2*v,l,m,a,b,x);
    }else if(a>m){
        upd(2*v+1,m+1,r,a,b,x);
    }else{
        upd(2*v,l,m,a,m,x);
        upd(2*v+1,m+1,r,m+1,b,x);
    }
    push(2*v);
    push(2*v+1);
    s[v]=max(s[2*v],s[2*v+1]);
}
ll get(ll v, ll l, ll r){
    push(v);
    if(l==r){
        return l;
    }
    ll m=(l+r)/2;
    if(s[2*v]+f[2*v]<=1){
        return get(2*v,l,m);
    }else{
        return get(2*v+1,m+1,r);
    }
}
signed main(){
    cin >> t;
    while(t--){
        stv.clear();
        sti.clear();
        ans=0;
        cin >> n >> m;
        build(1,0,m-1);
        for(i=0;i<m;i++){
            cin >> a[i];
        }
        cnt=0;
        for(i=m-1;i>=0;i--){
            if(a[i]>0){
            if(cnt<n){
                cnt++;
                stv.insert({a[i],i});
                sti.insert({i,a[i]});
            ans+=a[i];
            upd(1,0,m-1,0,i,1);
            }else{
                cnt--;
                if(stv.empty() || (*stv.begin()).first>=a[i]){
                    ans-=a[i];
                    upd(1,0,m-1,0,i,-1);
                }else{
                    ans+=a[i];
                    upd(1,0,m-1,0,i,1);
                    auto it=(*stv.begin());
                    ans-=2*it.first;
                    upd(1,0,m-1,0,it.second,-2);
                    sti.erase({it.second,it.first});
                    stv.erase(it);
                    stv.insert({a[i],i});
                    sti.insert({i,a[i]});
                }
            }
                j=get(1,0,m-1);
                while(!sti.empty() && (*sti.rbegin()).first>j){
                auto it=(*sti.rbegin());
                stv.erase({it.second,it.first});
                sti.erase(it);
                }
        }else{
            if(cnt==0){
                cnt++;
                stv.insert({a[i],i});
                sti.insert({i,a[i]});
            ans+=a[i];
            upd(1,0,m-1,0,i,1);
            }else{
                cnt--;
                    ans-=a[i];
                j=get(1,0,m-1);
                while(!sti.empty() && (*sti.rbegin()).first>=j){
                auto it=(*sti.rbegin());
                stv.erase({it.second,it.first});
                sti.erase(it);
                }
            }
        }
        }
    cout << ans << '\n';
    }
    return 0;
}