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

#pragma GCC optimize("O3")

using namespace std;
//using namespace __gnu_pbds;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define int long long

//typedef tree<int, null_type,less<int>,  rb_tree_tag, tree_order_statistics_node_update> ordered_set;

void solve(){
    int n, m;
    cin>>n>>m;
    vector<int> x(m);
    for(auto &y:x) cin>>y;
        vector<set<vector<int> > > dp(m+1);
        vector<int> st(n);
        dp[0].insert(st);
        for(int i = 0; i < m; ++i){
            set<vector<int> > f1, f2;
            int gg = 5;
            auto ndp = dp[i];
            while(!ndp.empty() && gg--){
                f1.insert(*ndp.begin());
                ndp.erase(ndp.begin());
            }
            gg = 5;
            ndp = dp[i];
            while(!ndp.empty() && gg--){
                f2.insert(*ndp.rbegin());
                ndp.erase(--ndp.end());
            }
            dp[i].clear();
            for(auto &y:f1) dp[i].insert(y);
            for(auto &y:f2) dp[i].insert(y);
            for(auto &l:dp[i]){
                for(int j = 0; j < n; ++j){
                    auto nw = l;
                    nw[j] = x[i] - nw[j];
                    dp[i+1].insert(nw);
                }
            }
            if (i){
                dp[i-1].clear();
            }
        }
        int ans = -4e18;
        for(auto &l:dp[m]){
            ans=max(ans, accumulate(l.begin(), l.end(), 0ll));
        }
        cout<<ans<<'\n';
        return;
}

signed main(){
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}
