#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,
        tree_order_statistics_node_update>;

#define int long long

struct nm {
    int val, plus, ind;
};

bool cmp(nm s1, nm s2) {
    return s1.val < s2.val;
}

int n;
vector<int> t_l, t_r;
vector<int> t_all;
vector<int> push_l, push_all;

void build(int v, int l, int r) {
    if (l + 1 == r) {
        t_l[v] = -l - 1;
        t_r[v] = l + 1;
        if (t_r[v] > n) {
            if (t_r[v] % 2 == n % 2) {
                t_r[v] = n;
            } else {
                t_r[v] = n - 1;
            }
        }
        t_all[v] = t_r[v] - t_l[v] - (l + 1) - (l + 1) % 2;
        return;
    }
    int m = (l + r) / 2;
    build(2 * v + 1, l, m);
    build(2 * v + 2, m, r);
    t_l[v] = min(t_l[2 * v + 1], t_l[2 * v + 2]);
    t_r[v] = max(t_r[2 * v + 1], t_r[2 * v + 2]);
    t_all[v] = min(t_all[2 * v + 1], t_all[2 * v + 2]);
}

void make_push(int v, int l, int r) {
    if (l + 1 != r) {
        t_l[2 * v + 1] += push_l[v];
        t_l[2 * v + 2] += push_l[v];
        t_all[2 * v + 1] -= push_l[v];
        t_all[2 * v + 2] -= push_l[v];
        push_l[2 * v + 1] += push_l[v];
        push_l[2 * v + 2] += push_l[v];
        push_l[v] = 0;
        t_all[2 * v + 1] += push_all[v];
        t_all[2 * v + 2] += push_all[v];
        push_all[v] = 0;
    }
}

int get_l(int v, int l, int r, int ql, int qr) {
    if (ql >= r || l >= qr) {
        return 1;
    }
    if (ql <= l && r <= qr) {
        return t_l[v];
    }
    make_push(v, l, r);
    int m = (l + r) / 2;
    return min(get_l(2 * v + 1, l, m, ql, qr), get_l(2 * v + 2, m, r, ql, qr));
}

void update1(int v, int l, int r, int ql, int qr, int x) {
    if (ql >= r || l >= qr) {
        return;
    }
    if (ql <= l && r <= qr) {
        t_l[v] += x;
        t_all[v] -= x;
        push_l[v] += x;
        return;
    }
    make_push(v, l, r);
    int m = (l + r) / 2;
    update1(2 * v + 1, l, m, ql, qr, x);
    update1(2 * v + 2, m, r, ql, qr, x);
    t_l[v] = min(t_l[2 * v + 1], t_l[2 * v + 2]);
    t_all[v] = min(t_all[2 * v + 1], t_all[2 * v + 2]);
}

void update_minl(int v, int l, int r, int ql, int qr, int x) {
    if (ql >= r || l >= qr) {
        return;
    }
    if (ql <= l && r <= qr) {
        if (t_l[v] >= 2) {
            return;
        }
        t_all[v] += x;
        push_all[v] += x;
        return;
    }
    make_push(v, l, r);
    int m = (l + r) / 2;
    update_minl(2 * v + 1, l, m, ql, qr, x);
    update_minl(2 * v + 2, m, r, ql, qr, x);
    t_all[v] = min(t_all[2 * v + 1], t_all[2 * v + 2]);
}

int get_mn(int v, int l, int r, int ql, int qr, int k);

int m;

signed main() {
    int tst;
    cin >> tst;
    while (tst--) {
        cin >> n >> m;
        vector<int> x(m);
        vector<nm> y(m);
        for (int i = 0; i < m; ++i) {
            cin >> x[i];
            y[i] = {abs(x[i]), 2 * (x[i] > 0) - 1, m - 1 - i};
        }
        if (n >= m) {
            cout << m * x[0] << '\n';
        } else {
            if (m % 2 == n % 2) {
                cout << m * x[0] << '\n';
            } else {
                cout << (m - 1) * x[0] << '\n';
            }
        }
        /*t_l.assign(4 * m, 0), t_r.assign(4 * m, 0), t_all.assign(4 * m, 0);
        push_l.assign(4 * m, 0), push_all.assign(4 * m, 0);
        build(0, 0, m);
        if (n == 1) {
            reverse(x.begin(), x.end());
            int s = 0;
            for (int i = 0; i < m; ++i) {
                if (i % 2 == 0) {
                    s += x[i];
                } else {
                    s -= x[i];
                }
            }
            cout << s << '\n';
            continue;
        }
        sort(y.begin(), y.end(), cmp);
        reverse(y.begin(), y.end());
        int s = 0;
        for (int i = 0; i < m; ++i) {
            int ind = y[i].ind, val = y[i].val, plus = y[i].plus;
            int r1;
            if (plus == 1) {
                int pr = get_l(0, 0, m, 0, ind);
                int l = ind - 1, r = m;
                while (r - l > 1) {
                    int mid = (l + r) / 2;
                    if (get_l(0, 0, m, 0, mid + 1) < pr) {
                        r = mid;
                    } else {
                        l = mid;
                    }
                }
                update1(0, 0, m, ind, m, 2);
                update_minl(0, 0, m, r, m, 2);
                r1 = r;
            }
            if (t_all[0] >= 0) {
                s += val;
            } else {
                update_minl(0, 0, m, r1, m, -2);
                update1(0, 0, m, ind, m, -2);
                s -= val;
            }
        }
        cout << s << '\n';*/
    }
    return 0;
}
