#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define ll long long 

int main() {
    ios_base::sync_with_stdio();
    cin.tie(0), cout.tie(0);
    ll tt;
    cin>>tt;
    for(ll ij=0;ij<tt;ij++){
        ll n,m;
        cin>>n>>m;
        vector<ll>s(m);
        ll sum=0;
        for(ll i=0 ;  i < m;i ++){
            cin>>s[i];
            sum+=abs(s[i]);
        }
        sum+=3;
        vector<vector<vector<bool>>>dp(m+1,vector<vector<bool>> (2*sum,vector<bool>(2*sum,false)));
        ll c=2*sum;
        dp[0][sum][sum]=true;
        for(ll i=1 ; i<= m; i ++){
            for(ll j=0; j<c;j++){
                for(ll k=0;k< c;k++){
                    if(dp[i-1][j][k]){
                        dp[i][-j+s[i-1]][k]=true;
                        dp[i][j][-k + s[i-1]]=true;
                    }
                }
            }
        }
        ll mx=-1e18;
        for(ll j=0; j<c;j++){
            for(ll k=0;k< c;k++){
                if(dp[m][j][k]){
                    mx=max(mx,j+k-sum-sum);
                }
            }
        }
        cout<<mx<<endl;
    }
}