#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <random>
#include <chrono>
using namespace std;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	ll t;
	cin >> t;
	while (t--) {
		ll n, m, mn = 0;
		cin >> n >> m;
		vector<ll> a(m), u(m, 0);
		for (ll i = 0; i < m; ++i) cin >> a[i], mn = min(mn, a[i]);
		set<pair<ll, ll>> s;
		ll b = n, sum = 0;
		for (ll i = m - 1; i >= 0; --i) {
			++b;
			sum -= a[i];
			if (b > 1) s.insert({ a[i], i });
			while (b > n) {
				auto it = s.end();
				--it;
				sum += 2 * (*it).first;
				u[(*it).second] = 1;
				s.erase(it);
				b -= 2;
			}
		}
		ll sum1 = sum;
		set<pair<ll, ll>> s1 = s;
		if (!u[0] && b > 1) {
			sum1 += 2 * a[0];
			b -= 2;
			s1.erase({ a[0], 0 });
		}
		while ((ll)s1.size() && b > 1) {
			auto it = s1.end();
			--it;
			if ((*it).first < 0) break;
			sum1 += 2 * (*it).first;
			s1.erase(it);
			b -= 2;
		}
		b = n - 1;
		while ((ll)s.size() && b > 1) {
			auto it = s.end();
			--it;
			if ((*it).first < 0) break;
			sum += 2 * (*it).first;
			s.erase(it);
			b -= 2;
		}
		cout << max(sum, sum1) << "\n";
	}
	cout << endl;
	return 0;
}