#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (auto &v : a)
        cin >> v;

    if (all_of(a.begin(), a.end(), [&](int v){return v == a[0];})) {
        m %= 2 * n;
        if (m < n)
            cout << a[0] * m << "\n";
        else
            cout << a[0] * n - a[0] * (m - n) << "\n";
        return;
    }
    int ans = LLONG_MIN;
    for (int mask = 0; mask < (1 << m); mask++) {
        int c0 = 0, c1 = 0;
        int sum = 0;
        for (int i = m - 1; i >= 0; i--) {
            if ((mask >> i) & 1) {
                if (c1)
                    sum -= a[i];
                else
                    sum += a[i];
                c1 = !c1;
            } else {
                if (c0)
                    sum -= a[i];
                else
                    sum += a[i];
                c0 = !c0;
            }
        }
        ans = max(ans, sum);
    }
    cout << ans << "\n";
}

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