#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pii = pair<int, int>;
constexpr char nl = '\n';

void solve() {
    int n, m;
    cin >> n >> m;
    vi a(m);
    ll ans = 0;
    ll mn = 1e10, mx = -1e10;
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        ans += a[i];
        mn = min(mn, (ll)a[i]);
        mx = max(mx, (ll)a[i]);
    }
    ll v = m - (m - n) / 2;
    int bal = 0;
    for (int i = m - 1; i >= 0; --i) {
        if (v > 0 && bal > 0 && a[i] == mn) {
            --bal;
            ans -= a[i];
            --v;
        } else {
            ++bal;
        }
    }
    ans -= v * mx;
    cout << ans << nl;
//    vvl dp(m, vl(n + 1, -1e15));
//    dp[m - 1][1] = a[m - 1];
//    for (int i = m - 2; i >= 0; --i) {
//        for (int j = 1; j <= n; ++j) {
//            dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + a[i]);
//        }
//        for (int j = 0; j < n; ++j) {
//            dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] - a[i]);
//        }
//    }
//    cout << *max_element(dp[0].begin(), dp[0].end()) << nl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
        solve();
}
