#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <math.h>
#include <string>
#include <vector>
#include <chrono>
#include <random>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <set>
#define endl '\n'

using namespace std;
using i64 = long long;
using ld = long double;

const i64 INF = 1e18 + 5;

mt19937 rnd(29);

const i64 S = 3e5 + 10, M = 401, K = 1005;
i64 a[S];

bool dp[M][K][K];

int main() {
	#ifdef _DEBUG
		freopen("input.txt", "r", stdin);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	i64 t; cin >> t;

	while (t--) {
		i64 n, m; cin >> n >> m;
		bool check = true;
		for (i64 x = 1; x <= m; ++x) {
			cin >> a[x];
			if (x > 1 && (a[x] != a[x - 1] || a[x] < 0)) check = false;
		}
		if (check) {
			i64 k = m / n;
			if (n >= m) {
				cout << a[1] * m << endl;
			}
			else {
				cout << a[1] * (m - ((m - n + 1) / 2)) - ((m - n + 1) / 2) * a[1] << endl;
			}
		}
		else {
			i64 ans = -INF;
			for (i64 x = 0; x < (i64(1) << m); ++x) {
				i64 sum = 0, sum1 = 0;
				i64 val = x;
				for (i64 y = 1; y <= m; ++y) {
					if ((val & 1) == 1) {
						sum = (a[y] - sum);
					}
					else {
						sum1 = (a[y] - sum1);
					}
					val = (val >> 1);
				}
				ans = max(ans, sum + sum1);
			}
			cout << ans << endl;
		}
	}

}