#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <random>
using namespace std;

#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define for0(i,n) for(ll i = 0; i < ll(n); i++)

typedef long long ll;
typedef double long dl;
typedef vector<ll> vll;
typedef vector<pair<ll,ll>> vpll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;


template<typename T1, typename T2>
ostream& operator <<(ostream& out, pair<T1, T2>& a){
    out << a.fi << " " << a.se << endl;
    return out;
}

template<typename T1, typename T2>
istream& operator <<(istream& in, pair<T1, T2>& a){
    in >> a.fi >> a.se;
    return in;
}

template<typename T>
istream& operator >>(istream& in, vector<T>& a){
    for(T& ai : a) in >> ai;
    return in;
}

template<typename T>
ostream& operator <<(ostream& out, vector<T>& a){
    for(T& ai : a) out << ai << " ";
    return out;
}

template<typename T>
istream& operator >>(istream& in, vector<vector<T>>& a){
    for(vector<T>& ai : a){
        for(T& aii : ai) in >> aii;
    }
    return in;
}

template<typename T>
ostream& operator <<(ostream& out, vector<vector<T>>& a){
    for(vector<T>& ai : a){
        for(T& aii : ai) out << aii << " ";
        out << endl;
    }
    return out;
}

int t;
int n, m;
vll xs;
ll iters = 1e6;

ll f(vi& v){
    vll a(n);
    ll s = 0;
    for0(i,m){
        s -= a[v[i]];
        a[v[i]] = xs[i] - a[v[i]];
        s += a[v[i]];
    }
    return s;
}

dl rnd(){
    return 1 / (rand() - rand());
}

void solve(){
    cin >> n >> m;
    xs = vll(m);
    cin >> xs;

    vi v;
    for0(i,m){
        v.pub(rand() % n);
    }

    ll ans = f(v);
    ll best = ans;
    dl t = 1;

    ll itersc = iters;
    if (m >= 9){
        itersc = 2500000;
    }
    if (m >= 13){
        itersc = 5000000;
    }

    for (int i = 0; i < itersc; i++) {
        t *= 0.99;
        vi u = v;
        u[rand() % m] = rand() % n;
        ll val = f(u);
        best = max(best, val);
        if (val > ans || rnd() < exp((val - ans) / t)) {
            v = u;
            ans = val;
        }
    }
    cout << best << endl;
}

int main()
{
    srand(42);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    iters /= t;
    while(t--)solve();
    return 0;
}
/*
4
1 4
1 2 3 4
2 7
10 3 7 1 4 6 3
4 10
103 354 1 227 179 189 142 201 165 140
5 3
-10 11 -4
*/
