#pragma GCC optimize("arch=skylake")
#pragma GCC optimize("Ofast,inline")

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define fi first
#define se second
mt19937 gen(time(0));

void solve() {
    int n, m;
    cin >> n >> m;
    int x[m];
    for(int i = 0; i < m; ++i) {
        cin >> x[i];
    }
    if(n > m) {
        cout << x[0] * m << '\n';
        return;
    }
    int ans = min(n, m) * x[0];
    if((n % 2) == (m % 2)) {
        cout << ans << '\n';
    } else {
        cout << ans - x[0] << '\n';
    }
    return;
}

int32_t main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int qq;
    cin >> qq;
    while(qq--) {
        solve();
    }
    return 0;
}
