#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;
    }
    int mx=-INF;
    for (int i=0;i<(1<<m);++i){
        int f=0,s=0;
        for (int j=0;j<m;++j){
            if ((i&(1<<j))!=0){
                s=(a[j]-s);
            }
            else{
                f=(a[j]-f);
            }
        }
        mx=max(mx,f+s);
    }
    cout<<mx<<endl;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin>>t;
    while (t--){
        solve();
    }
}