#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <cmath>
#include <chrono>
#include <random>
#define endl '\n'
#define ALL(v) v.begin(), v.end()
#define current_time chrono::steady_clock().now().time_since_epoch().count()

using namespace std;

template <typename T1, typename T2>
bool rmin(T1& x, const T2& y)
{
	if (y < x)
	{
		x = y;
		return true;
	}
	return false;
}
template <typename T1, typename T2>
bool rmax(T1& x, const T2& y)
{
	if (x < y)
	{
		x = y;
		return true;
	}
	return false;
}

constexpr uint32_t MOD = 998'244'353, MOD_phi = MOD - 1;

struct Mod_int
{
	uint32_t val;

	Mod_int& operator+=(const Mod_int& a)
	{
		if ((val += a.val) >= MOD)
		{
			val -= MOD;
		}
		return *this;
	}
	Mod_int& operator-=(const Mod_int& a)
	{
		if ((val -= a.val) & 0x80'00'00'00)
		{
			val += MOD;
		}
		return *this;
	}
	Mod_int& operator*=(const Mod_int& a)
	{
		val = int64_t(val) * a.val % MOD;
		return *this;
	}

	friend Mod_int operator+(const Mod_int& a, const Mod_int& b)
	{
		return Mod_int(a) += b;
	}
	friend Mod_int operator-(const Mod_int& a, const Mod_int& b)
	{
		return Mod_int(a) -= b;
	}
	friend Mod_int operator*(const Mod_int& a, const Mod_int& b)
	{
		return Mod_int(a) *= b;
	}

	Mod_int pow(uint64_t pow_val) const
	{
		Mod_int ans{ 1 }, mlt{ val };
		while (pow_val)
		{
			if (pow_val & 1)
			{
				ans *= mlt;
			}
			mlt *= mlt;
			pow_val >>= 1;
		}
		return ans;
	}

	Mod_int& operator/=(const Mod_int& a)
	{
		return *this *= a.pow(MOD_phi - 1);
	}

	friend Mod_int operator/(const Mod_int& a, const Mod_int& b)
	{
		return Mod_int(a) /= b;
	}
};

constexpr int32_t INF = 2'000'000'001;
constexpr int64_t INFl = 2'000'000'000'000'000'001;

void solve();

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

	int t = 1;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		solve();
		cout << endl;
	}

	return 0;
}

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> mas(m);
	for (int i = 0; i < m; i++)
	{
		cin >> mas[i];
	}
	reverse(ALL(mas));
	multiset<int, greater<int>> dif;
	for (int i = 0; i < n / 2; i++)
	{
		dif.insert(-INF);
	}
	int64_t val0 = 0;
	for (int i = 0; i < m; i++)
	{
		if (i & 1)
		{
			val0 -= mas[i];
			dif.insert(2 * mas[i]);
			dif.erase(prev(dif.end()));
		}
		else
		{
			val0 += mas[i];
			if (!dif.empty() and *dif.begin() > 2 * mas[i])
			{
				val0 += *dif.begin() - 2 * mas[i];
			}
			dif.insert(2 * mas[i]);
			dif.erase(dif.begin());
			if (~n & 1)
			{
				dif.erase(prev(dif.end()));
				dif.insert(-INF);
			}
		}
	}
	int64_t ans = val0, cur = val0;
	multiset<int>::iterator it = dif.begin();
	while (it != dif.end())
	{
		cur += *it;
		rmax(ans, cur);
		++it;
	}
	cout << ans;

	return;
}