#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <bitset>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <random>

using namespace std;

// random_device rd;
mt19937 rnd(57575757);

int gen(int l, int r) {
    return (rnd() % (r - l + 1)) + l;
}

// #define int long long
using pii = pair<int, int>;

const int lim = 2e6 + 3e5, c = 1e5;

double gen_double() {
    return double(gen(0, c)) / double(c);
}

void solve() {
    int n, m;
    cin >> n >> m;
    // vector<int> a(n, 0);
    vector<int> vq(m);
    for (int i = 0; i < m; i++) {
        cin >> vq[i];
    }
    int res = -1e9;
    vector<int> a(n);
    vector<int> ord;
    for (int i = 0; i < m; i++) {
        ord.push_back(0);
    }
    auto calc_f = [&] () -> int {
        fill(a.begin(), a.end(), 0);
        for (int i = 0; i < m; i++) {
            a[ord[i]] = vq[i] - a[ord[i]];
        }
        int temp = 0;
        for (int i : a) {
            temp += i;
        }
        res = max(res, temp);
        return temp;
    };
    int fp = calc_f();
    int op = 0;
    double t = 1.0;
    while (op < lim) {
        op++;
        t -= 1 / double(lim) * 0.6;
        int id = gen(0, m - 1);
        int val = ord[id] ^ 1;
        int old = ord[id];
        ord[id] = val;
        int fn = calc_f();
        if (fn > fp || gen_double() < 1.3 * exp((fn - fp) / t * 0.14)) {
            fp = fn;
        } else {
            ord[id] = old;
        }
    }
    cout << res << '\n';
}

/*
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
 */

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        solve();
    }
}
