#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 = 200, K = 201 * 201 * 2;
i64 a[S];

pair<bool, i64> dp[M][K], dpNxt[M][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, mid = K / 2; // mid == 0

			for (i64 x = 0; x <= m; ++x) {
				for (i64 y = 0; y < K; ++y) {
					dp[x][y] = { false, -1 };
				}
			}
			dp[0][mid] = { true, mid };

			for (i64 x = 1; x <= m; ++x) {
				for (i64 y = K - 1; y >= 0; --y) {
					if (dp[x - 1][y].first) {
						i64 sum1 = y - mid, sum2 = dp[x - 1][y].second - mid;
						dpNxt[x][(a[x] - sum1) + mid] = { true, dp[x - 1][y].second };
						dpNxt[x][sum1 + mid] = { true, (a[x] - sum2) + mid };
					}
				}
				for (i64 y = 0; y < K; ++y) {
					dp[x][y] = dpNxt[x][y];
				}
			}

			for (i64 y = 0; y < K; ++y) {
				if (dp[m][y].first) {
					i64 ch1 = y - mid, ch2 = dp[m][y].second - mid;
					ans = max(ans, ch1 + ch2);
				}
			}
			cout << ans << endl;
		}
	}

}