#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define ll long long 

int main() {
    ios_base::sync_with_stdio();
    cin.tie(0), cout.tie(0);
    ll tt;
    cin>>tt;
    for(ll ij=0;ij<tt;ij++){
        ll n,m;
        cin>>n>>m;
        multiset<ll>st;
        for(ll i=0 ;i < n;i++){
            st.insert(0);
        }
        vector<ll>z;
        ll last1,last2 ;
        for(ll i=0;i<m;i++){
            ll mn=*st.begin();
            ll mx=*st.rbegin();
            ll x;
            cin>>x;
            z.push_back(x);
            if(x>=0){
                st.erase(st.find(mn));
                st.insert(-mn + x);
                last1=mn;
                last2 = -mn + x;
            }else{
                st.erase(st.find(mx));
                st.insert(-mx + x);
                last1=mx;
                last2 = -mx + x;
            }
        }
        if(*st.begin() >= 0) { 
            ll ans=0;
            for(auto el:st){
                ans+=el;
            }
            cout<<ans<<endl;
        }else{
            ll ans=0;
            for(auto el:st){
                ans+=el;
            }
            ll mx=ans;
            ans=0;
            st.erase(st.find(last2));
            st.insert(last1);
            ll x = z[z.size()-1];
            ll mn=*st.begin();
            ll mx=*st.rbegin();
            if(x<0){
                st.erase(st.find(mn));
                st.insert(-mn + x);
            }else{
                st.erase(st.find(mx));
                st.insert(-mx + x);
            }
            ll ans=0;
            for(auto el:st){
                ans+=el;
            }
            cout<<max(ans,mx);
        }
    }
}
