// semenInRussia 2025
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

const int N = 30, S = 600;
int offset = 600;
bool dp[N][S * 2][S * 2];

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> x(m);

  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < S * 2; j++) {
      for (int k = 0; k < S * 2; k++) {
        dp[i][j][k] = false;
      }
    }
  }

  for (auto &v : x) {
    cin >> v;
  }

  dp[0][offset][offset] = true;
  for (int i = 0; i <= m; i++) {
    for (int a = -S; a < S; a++) {
      for (int b = -S; b < S; b++) {
        if (dp[i][a + offset][b + offset] == false) {
          continue;
        }
        // cerr << i << ". " << "we can do " << a << "+" << b << endl;
        dp[i + 1][x[i] - a + offset][b + offset] = true;
        dp[i + 1][a + offset][x[i] - b + offset] = true;
      }
    }
  }

  int64_t ans = -1e18 - 100;
  for (int64_t a = -S; a < S; a++) {
    for (int64_t b = -S; b < S; b++) {
      if (dp[m][a + offset][b + offset]) {
        ans = max(ans, a + b);
      }
    }
  }

  cout << ans << "\n";
}

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    solve();
  }
}