#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <immintrin.h>
#include <numeric>

using ll = long long;
using ld = long double;
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	// ooshp 2024-2025 zakluchitelnuy tur
	// Code is written by Mark_Pr (c) 2025
	int t;
	cin >> t;
	while (t--)
	{
		int n, m;
		cin >> n >> m;
		vector <ll> x(m);
		for (auto& i : x)
		{
			cin >> i;
		}
		if (n >= m)
		{
			cout << accumulate(x.begin(), x.end(), 0ll) << '\n';
			continue;
		}
		ll x1 = *min_element(x.begin(), x.end());
		ll x2 = *max_element(x.begin(), x.end());
		ll ans = 0;
		int bal = 0;
		for (auto& i : x)
		{
			if (bal > 0 && i == x1)
			{
				bal--;
				ans -= x1;
			}
			else if (bal == n)
			{
				bal--;
				ans -= i;
			}
			else
			{
				ans += i;
				bal++;
			}
		}
		if ((m - n) % 2 == 1)
			n--;
		cout << (1ll * n - bal) * x1 + ans << '\n';
	}
	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
