#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <unordered_map>
#include <algorithm>
#include <queue>
using namespace std;

using ll = long long;

const int maxn = 5e5;
const ll inf = 1e16 + 239;

ll solve1(vector<ll>& a, int n) {
  int sz = a.size();
  vector<ll> b = a;
  sort(b.begin(), b.end());
  ll med = b[(sz + 1) / 2];

  vector<int> p(sz, 0);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
  ll ans = 0;
  for (int i = sz - 1; i >= 0; i--) {
    if (q.empty()) {
      q.push({ a[i], -i });
      continue;
    }
    if (a[i] >= med) {
      q.push({ a[i], -i });
    }
    else {
      ans += +q.top().first - a[i];
      p[i] = -q.top().second;
      p[-q.top().second] = i;
      q.pop();
    }
  }
  q = {};
  for (int i = sz - 1; i >= 0; i--) {
    if (p[i] != -1) continue;
    if (q.empty()) {
      q.push({ a[i], -i });
      continue;
    }
    if (a[i] >= 0 && q.empty()) {
      break;
    }
    ans += -q.top().first + a[i];
    p[i] = -q.top().second;
    p[-q.top().second] = i;
    q.pop();
  }
  vector<ll> rem(0);
  for (int i = 0; i < sz; i++) {
    if (p[i] == -1) {
      rem.push_back(a[i]);
    }
  }
  if (rem.size() <= n) {
    for (ll x : rem) {
      ans += x;
    }
    return ans;
  }
  return ans + solve1(rem, n);

}


void solve() {
  int n, m;
  cin >> n >> m;
  vector<ll> a(2);
  vector<ll> x(m);
  for (int i = 0; i < m; i++) {
    cin >> x[i];
  }
  ll ans = -inf;
  for (int mask = 0; mask < (1 << m); mask++) {
    a[0] = 0;
    a[1] = 0;
    for (int i = 0; i < m; i++) {
      int j = (mask >> i) & 1;
      a[j] = x[i] - a[j];
    }
    ans = max(ans, a[0] + a[1]);
  }
  cout << ans << '\n';
}

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