
#include<bits/stdc++.h>

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin() , x.rend()
#define f first
#define second

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pi = pair<int , int>;
using vpi = vector<pi>;


const int mod = 1e9 + 7;

ll summ(int a , int b , const int &mod) {
    return ((a + b) % mod + mod) % mod;
}
ll mn(int a , int b , const int &mod) {
    return ((a - b) % mod + mod) % mod;
}
ll umn(int a , int b , const int &mod) {
    return ((a * b) % mod + mod) % mod;
}
int binpow(int a , int p) {
    if (p == 0) return 1;
    if (p & 1) {
        return umn(a , binpow(a , p - 1) , mod);
    } else {
        int x = binpow(a , p / 2);
        return umn(x , x , mod);
    }
}

int del(int a , int b , const int &mod) {
    return umn(a , binpow(b , mod - 2) , mod);
}

struct node {
    int ans , cnt , mx , pos;
};
bool operator<(const node a , const node b) {
    return ((a.mx == b.mx ? a.pos < b.pos : a.mx < b.mx));
}

struct pope {
    int x , ind;
};

void solve() {
    int n , m;
    cin >> n >> m;
    vector<int> x(m);
    map<int , int> mp;
    for(int i = 0 ; i < m ; i++) {
        cin >> x[i];
        mp[x[i]]++;
    }
    if (mp.size() == 1) {
        if(n >= m) {
            cout << x[0] * m << '\n';
            return;
        }
        cout << x[0] * (n - 1) + ((m - n + 1) % 2) * x[0] << '\n';
    } else {
        vector<int> a;
        for(auto [x , y] : mp) {
            a.push_back(x);
        }
        int cnt1 = mp[a[0]];
        int cnt2 = mp[a[1]];
        if(cnt1 + cnt2 <= n) {
            cout << cnt1 * a[0] + cnt2 * a[1] << '\n';
        } else {
            if (cnt2 < n) {
                int x = n - cnt2;
                cout << cnt2 * a[1] + (x - 1) * a[0] + ((cnt1 - x + 1) % 2) * a[0] << '\n';
            } else {
                int y = (cnt2 - n + 1) % 2;
                int z = (cnt1) % 2;
                if (x[m - 1] == a[1]) {
                    if(z == 0) {
                        cout << (n - 1) * a[1] + y * a[1] << '\n';
                    } else {
                        cout << (n - 1) * a[1] + y * a[1] - a[0] << '\n';
                    }
                } else {
                    if(z == 0) {
                        cout << (n - 1) * a[1] + y * a[1] << '\n';
                    } else {
                        cout << (n - 1) * a[1] - y * a[1] - a[0] << '\n';
                    }
                }
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
}


