#include "bits/stdc++.h"
#include "numeric"
using namespace std;

#define forn(i, n) for(int i=0;i<n;++i)
#define fornn(i, l, r) for(int i=l;i<=r;++i)
#define ford(i, n) for(int i=n-1;i>=0;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int maxn = 1e5 + 7;
const int logn = 32;
const int mod = 1e9 + 7;
const int iterations = 5e5;

int n,m;
vector<ll> x;

double rnd() { return (double)rand() / RAND_MAX; }

ll f(vector<int> c) {
    vector<ll> b(n,0);
    forn(i,m) b[c[i]]=x[i]-b[c[i]];
    ll res =0;
    forn(i,n) res+=b[i];
    return res;
}

ll annealing() {
    std::random_device r;

    vector<int> v(m,0);
    forn(i,m) v[i]=r()%n;
    ll ans=f(v);

    double t=1;
    forn(it, iterations) {
        t*=0.99;

        vector<int> u=v;
        int index=r()%m;
        u[index]=(u[index]+1)%2;
        int cur = f(u);

        if (cur>ans || (rnd() < exp((cur-ans)/t))) {
            v=u;
            ans=cur;
        }
    }
    return ans;
}

void solve() {
    cin>>n>>m;
    x.assign(m, 0);
    forn(i,m) cin>>x[i];
    cout<<annealing()<<endl;
}

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

#ifdef LOCAL
    freopen("C:\\work\\untitled\\b.txt", "r", stdin);
    freopen("C:\\work\\untitled\\out.txt", "w", stdout);

    while (!cin.eof()) {
        solve();
        cout << endl;
    }
#else
    int t; cin>>t;
    while(t--){
        solve();
    }
#endif

    return 0;
}
