#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef long long ll;

void solve();

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1; cin >> tt;
    while (tt--) {
        solve();
        cout << "\n";
    }
}

void solve() {
    int n, m; cin >> n >> m;
    vector<ll> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];
    if (m <= n || a[0] <= 0) {
        cout << a[0] * m;
        return;
    }
    ll ans = a[0] * (m - 1);
    if ((n - m) % 2 == 0) ans += a[0];
    cout << ans;
}
