#ifndef LOCAL
  #pragma GCC optimize("Ofast,unroll-loops")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#ifndef LOCAL
  #pragma GCC target("avx,avx2,fma")
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<ll> a(m);
  for (auto& it : a) cin >> it;
  set<vector<ll>> dp, ndp;
  dp.insert(vector<ll>(n));
  for (int i = 0; i < m; ++i) {
    for (auto vec : dp) {
      for (int j = 0; j < n; ++j) {
        int t = vec[j];
        vec[j] = a[i] - vec[j];
        ndp.insert(vec);
        vec[j] = t;
      }
    }
    dp = ndp;
    ndp.clear();
    for (int j = 0; j < 50; ++j) {
      if (dp.empty()) break;
      auto k = *dp.begin();
      ndp.insert(k);
      dp.erase(dp.begin());
    }
    for (int j = 0; j < 50; ++j) {
      if (dp.empty()) break;
      auto k = *dp.rbegin();
      ndp.insert(k);
      dp.erase(k);
    }
    dp = ndp;
    ndp.clear();
  }
  ll ans = -1e17;
  for (auto& vec : dp) ans = max(ans, accumulate(vec.begin(), vec.end(), 0LL));
  cout << ans << '\n';
}

signed main() {
  // freopen("in", "r", stdin);
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    solve();
  }
}