#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

mt19937_64 rnd(1488);

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> X(m);
    map<int, int> M;
    int ma = -1e18, mi = 1e18;
    int ml, mf = 1e9;
    for (int i = 0; i < m; ++i) {
        cin >> X[i];
        ++M[X[i]];
        ma = max(X[i], ma);
        mi = min(X[i], mi);
    }
    if (ma == mi) {
        if (n >= m) {
            cout << m * ma << endl;
        } else {
            cout << (n - (m - n) % 2) * ma << endl;
        }
        return;
    }
    if (M[ma] > n && (M[ma] - n) % 2 == 1) {
        M[ma] = n - 1;
    }
    M[ma] = min(n, M[ma]);
    int cr = min(M[mi], n - M[ma]);
    if ((M[ma] - cr) % 2 == 0 || cr == M[ma]) {
        cout << M[ma] * ma + cr * mi << endl;
        return;
    }
    for (int i = 0; i < m; ++i) {
        if (X[i] == ma) {
            ml = i;
        } else {
            mf = min(mf, i);
        }
    }
    if (ml < mf && cr == 0) {
        cout << 1 * mi + (M[ma] - 2) * ma;
    } else {
        cout << (cr - 1) * mi + M[ma] * ma;
    }
    cout << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a;
    cin >> a;
    for (int i = 0; i < a; ++i) {
        solve();
    }
}

