#ifdef _DEBUG
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <limits>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <chrono>
#include <random>
#include <assert.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using ld = long double;
using pii = pair<int, int>;
using pli = pair<long long, int>;
using pil = pair<int, long long>;
using pll = pair<long long, long long>;
template <typename T>
using uset = unordered_set<T>;
template <typename T1, typename T2>
using umap = unordered_map<T1, T2>;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const ll inf = 3e18;

void smax(ll& a, ll b) {
	a = max(a, b);
}

inline void solve() {
	int n, m;
	cin >> n >> m;
	vector<ll> x(m);
	for (int i = 0; i < m; i++)
		cin >> x[i];
	int min_bal = 0;
	int bal_parity = 0;
	if ((n ^ m) & 1)
		bal_parity = 1;
	map<int, ll> save;
	auto calc = [&](int init_bal) -> ll {
		if (save.count(init_bal))
			return save[init_bal];
		min_bal = init_bal;
		ll dp0 = 0;
		multiset<ll> st;
		for (int i = 0; i < m; i++) {
			dp0 -= x[i];
			st.insert(-2 * x[i]);
			if (min_bal == 0)
				min_bal++;
			else
				min_bal--;
			if (min_bal == 1) {
				dp0 -= *st.begin();
				st.erase(st.begin());
			}
			if (min_bal + 2 * st.size() > n)
				st.erase(--st.end());
		}
		for (auto i : st)
			dp0 -= i;
		return save[init_bal] = dp0;
	};
	int lo = bal_parity - 2;
	int hi = n;
	if ((hi - bal_parity) & 1)
		hi--;
	while (hi - lo > 2) {
		int mid = (lo + hi) / 2;
		if ((hi - mid) & 1)
			mid++;
		ll a1 = calc(mid);
		ll a2 = calc(mid + 1);
		if (a1 > a2)
			hi = mid;
		else
			lo = mid;
	}
	cout << calc(hi) << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#ifdef _DEBUG
	freopen("01.dat", "r", stdin);
#endif
	int tt = 1;
	cin >> tt;
	for (int test_id = 1; test_id <= tt; test_id++) {
#ifdef _DEBUG
		cout << "TESTCASE# " << test_id << '\n';
#endif
		solve();
	}
	return 0;
}
