#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5;
const int chg = 1;
const long double an = 0.9;
long double temp = 1;

mt19937 rng(time(0));

int n;
vector<long long> b;

long long cost(vector<int>& path) {
    vector<long long> tempa(n);
    for (int i = 0; i < path.size(); ++i) {
        int it = path[i];
        tempa[it] = b[i] - tempa[it];
    }

    long long sum = 0;
    for (int i = 0; i < n; ++i) sum += tempa[i];
    return sum;
}

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    srand(time(0));
    
    int t;
    cin >> t;
    
    while (t--) {
        int m;
        cin >> n >> m;
        
        b.assign(m, 0);
        for (int i = 0; i < m; ++i) {
            cin >> b[i];
        }
        
        vector<int> path, best_path;
        for (int i = 0; i < m; ++i) {
            path.push_back(rng() % n);
        }

        long long mx = cost(path);
        best_path = path;

        for (int i = 0; i < N; ++i) {
            path = best_path;
            for (int j = 0; j < chg; ++j) {
                int it = rng() % m;
                path[it] = rng() % n;
            }

            long long cur_cost = cost(path);
            if (mx < cur_cost || exp(cur_cost - mx) < temp) {
                mx = cur_cost;
                best_path = path;
            }

            temp *= an;
        }

        cout << mx << "\n";
    }

    return 0;
}
