#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);
}

#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx,avx2")

struct segtree {
	vector<int> tree;
	vector<ll> c;
	int sz;

	segtree() {}

	segtree(const vector<ll>& _c) {
		c = _c;
		sz = c.size();
		tree.assign(4 * sz, 0);
	}

	void add(int i, int v, int tl, int tr) {
		while (true) {
			tree[v]++;
			if (tr - tl == 1)
				return;
			int m = (tl + tr) / 2;
			if (i < m)
				v = 2 * v + 1, tr = m;
			else
				v = 2 * v + 2, tl = m;
		}
	}

	void add(int i) {
		add(i, 0, 0, sz);
	}

	ll del_min(int v, int tl, int tr) {
		while (true) {
			tree[v]--;
			if (tr - tl == 1)
				return c[tl];
			int m = (tl + tr) / 2;
			if (tree[2 * v + 1])
				v = 2 * v + 1, tr = m;
			else
				v = 2 * v + 2, tl = m;
		}
	}

	ll del_min() {
		return del_min(0, 0, sz);
	}

	ll del_max(int v, int tl, int tr) {
		while (true) {
			tree[v]--;
			if (tr - tl == 1)
				return c[tl];
			int m = (tl + tr) / 2;
			if (tree[2 * v + 2])
				v = 2 * v + 2, tl = m;
			else
				v = 2 * v + 1, tr = m;
		}
	}

	ll del_max() {
		return del_max(0, 0, sz);
	}

	ll sum(int v, int tl, int tr) {
		if (tr - tl == 1)
			return c[tl] * tree[v];
		int m = (tl + tr) / 2;
		return sum(2 * v + 1, tl, m) + sum(2 * v + 2, m, tr);
	}

	ll sum() {
		return sum(0, 0, sz);
	}
};

umap<int, ll> save;
int n, m;
const int N = 3e5;
ll x[N];
vector<ll> c;

ll calc(int init_bal) {
	if (save.count(init_bal))
		return save[init_bal];
	int min_bal = init_bal;
	ll dp0 = 0;
	segtree st(c);
	int size = 0;
	ll sum = 0;
	for (int i = 0; i < m; i++) {
		dp0 -= c[x[i]];
		sum += c[x[i]];
		st.add(x[i]);
		size++;
		bool was0 = min_bal == 0;
		if (min_bal == 0)
			min_bal++;
		else
			min_bal--;
		if (was0) {
			ll mx = st.del_max();
			dp0 += 2 * mx, size--;
			sum -= mx;
		}
		if (min_bal + 2 * size > n)
			sum -= st.del_min(), size--;
	}
	dp0 += 2 * sum;
	return save[init_bal] = dp0;
}

inline void solve() {
	save.clear();
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> x[i];
	c.assign(m, 0);
	for (int i = 0; i < m; i++)
		c[i] = x[i];
	sort(all(c));
	c.resize(unique(all(c)) - c.begin());
	for (int i = 0; i < m; i++)
		x[i] = lower_bound(all(c), x[i]) - c.begin();
	int min_bal = 0;
	int bal_parity = 0;
	if ((n ^ m) & 1)
		bal_parity = 1;
	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 + 2);
		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;
}
