#pragma GCC optimize("O3, Ofast, unroll-loops, inline, no-stack-protector")
#include <bits/stdc++.h>
#pragma GCC target("avx2")

using namespace std;

using ll = long long;
using pii = pair<int, int>;

vector<vector<int>> g;
vector<int> cnt, s;
ll ans = -1e18;


void gen(vector<ll> &a, vector<ll> &x, int ptr) {
    if (ptr == x.size()) {
        ll sum = 0;
        for (auto el : a) sum += el;
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i < a.size(); ++i) {
        ll last = a[i];
        a[i] = x[ptr] - a[i];
        gen(a, x, ptr + 1);
        a[i] = last;
    }
}

random_device rd;
mt19937 rng(rd());
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t --> 0) {
        int n, m;
        cin >> n >> m;
        vector<ll> a(n);
        vector<ll> x(m);
        for (int i = 0; i < m; ++i) {
            cin >> x[i];
        }
        unordered_map<int, vector<int>> mp, mp2;
        mp[0].push_back(0);
        for (auto el : x) {
            for (auto& p : mp) {
                auto [i, j] = p;
                for (auto j1 : j) {
                    mp2[el - i].push_back(j1);
                    mp2[i].push_back(el - j1);
                }
            }
            swap(mp, mp2);
            mp2.clear();
        }
        ans = -1e18;
        for (auto& [i, j] : mp) {
            for (auto j1 : j) {
                ans = max(ans, 1ll * i + j1);
            }
        }
        cout << ans << "\n";
    }
}
