#include<bits/stdc++.h>
//#pragma GCCoptimize("Ofast,unroll-loops")
using namespace std;
#define int long long
#define ns cout << "\n";
#define ld long double
const int INF=1e18,N=1e6;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int>a(m);
    for (auto &i:a){
        cin>>i;
    }
    if (*min_element(a.begin(),a.end())>=0 && *min_element(a.begin(),a.end())==*max_element(a.begin(),a.end())){
         if (m<n){
            cout<<a[0]*m<<endl;
        }
        else{
            int w=a[0]*n;
            if ((m-n)%2==0){
                cout<<w;
            }
            else{
                cout<<w-a[0];
            }
            cout<<endl;
        }
        return;
    }
    map<pair<int,int>,int>dp;
    dp[{0,0}]=1;
    for (int i=0;i<m;++i){
        map<pair<int,int>,int> dpo;
        for (auto j:dp){
            dpo[{a[i]-j.first.first,j.first.second}]=1;
            dpo[{j.first.first,a[i]-j.first.second}]=1;
        }
        dp=dpo;
    }
    int w=-INF;
    for (auto i:dp){
        w=max(w,i.first.first+i.first.second);
    }
    cout<<w<<endl;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin>>t;
    while (t--){
        solve();
    }
}