#include <iostream>

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ll t;
    cin >> t;
    for (int _ = 0; _ < t; ++_){
        ll n, m;
        cin >> n >> m;
        vector<ll> x(m);
        ll check = 0;
        bool g1 = true;
        for (int i = 0; i < m; ++i){
            cin >> x[i];
            if (i == 0){
                check = x[i];
            } else{
                if (check != x[i]){
                    g1 = false;
                }
            }
        }
        if (g1){
            if (check <= 0){
                cout << check * (m % 2) << endl;
            } else{
                if (m <= n){
                    cout << m * check << endl;
                } else{
                    cout << check * n - check * (m - n + 1) / 2;
                }
            }
            continue;
        }
        else {
            reverse(x.begin(), x.end());
            vector<vector<vector<ll>>> dp(m, vector<vector<ll>>(n + 1, vector<ll>(2, -1e18)));
            dp[0][1][1] = x[0];
            ll ans = -1e18;
            for (int i = 1; i < m; ++i){
                for (int j = 0; j < n + 1; ++j){
                    if (j < n){
                        dp[i][j][0] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) - x[i];
                    }
                    if (j > 0){
                        dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + x[i];
                    }
                }
            }
            for (int i = 0; i < n + 1; ++i){
                ans = max(ans, max(dp[m - 1][i][0], dp[m - 1][i][1]));
            }
            cout << ans << endl;
        }
    }
    return 0;
}


/*
int main()
{
    ll t;
    cin >> t;
    for (int _ = 0; _ < t; ++_){
        ll n, m;
        cin >> n >> m;
        vector<ll> x(m);
        ll check = 0;
        bool g1 = true;
        for (int i = 0; i < m; ++i){
            cin >> x[i];
            if (i == 0){
                check = x[i];
                if (x[i] > 0){
                    g1 = false;
                }
            } else{
                if (check != x[i]){
                    g1 = false;
                }
            }
        }
        if (g1){
            cout << check * (m % 2) << endl;
            continue;
        }
        else {
            reverse(x.begin(), x.end());
            vector<vector<vector<ll>>> dp(m, vector<vector<ll>>(n + 1, vector<ll>(2, -1e18)));
            dp[0][1][1] = x[0];
            ll ans = -1e18;
            for (int i = 1; i < m; ++i){
                for (int j = 0; j < n + 1; ++j){
                    if (j < n){
                        dp[i][j][0] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) - x[i];
                    }
                    if (j > 0){
                        dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + x[i];
                    }
                }
            }
            for (int i = 0; i < n + 1; ++i){
                ans = max(ans, max(dp[m - 1][i][0], dp[m - 1][i][1]));
            }
            cout << ans << endl;
        }
    }
    return 0;
}
*/

/*
vector<ll> st, a;

void build(int v, int tl, int tr){
    if (tl == tr){
        st[v] = a[tl];
    } else{
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        st[v] = st[2 * v] + st[2 * v + 1];
    }
}

void upd(int v, int tl, int tr, int ind, int val){
    if (tl == tr){
        st[v] = val;
        a[ind] = val;
    } else{
        int tm = (tl + tr) / 2;
        if (ind <= tm){
            upd(2 * v, tl, tm, ind, val);
        } else{
            upd(2 * v + 1, tm + 1, tr, ind, val);
        }
        st[v] = st[2 * v] + st[2 * v + 1];
    }
}

ll getVal(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r){
        return st[v];
    } else{
        int tm = (tl + tr) / 2;
        if (r <= tm){
            return getVal(2 * v, tl, tm, l, r);
        }
        if (l > tm){
            return getVal(2 * v + 1, tm + 1, tr, l, r);
        }
        return getVal(2 * v, tl, tm, l, r) + getVal(2 * v + 1, tm + 1, tr, l, r);
    }
}*/

/*
vector<ll> st, stop, order, h, sz, tin, s, a, p, pos;
vector<vector<ll>> g;
ll gtin = 0;

void dfs1(int v){
    ll msz = 0, ind = 0;
    for (int i = 0; i < g[v].size(); ++i){
        int u = g[v][i];
        dfs1(u);
        sz[v] += sz[u];
        if (sz[u] >= msz){
            ind = i;
            msz = sz[u];
        }
    }
    sz[v]++;
    if (sz[v] > 1){
        swap(g[v][0], g[v][ind]);
    }
}

void dfs2(int v, int head){
    order.push_back(v);
    h[v] = head;
    tin[v] = gtin;
    if (sz[v] > 1){
        gtin++;
        dfs2(g[v][0], head);
        for (int i = 1; i < g[v].size(); ++i){
            int u = g[v][i];
            gtin++;
            dfs2(u, u);
        }
    }
}

void bfs(int v){
    priority_queue<pair<ll, ll>> q;
    q.push({s[v], v});
    int j = 0;
    while (!q.empty()){
        ll u = q.top().second;
        q.pop();
        a.push_back(u);
        pos[u] = j;
        for (int w: g[u]){
            q.push({s[w], w});
        }
        j++;
    }
}

void upd(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r){
        st[v] += 1;
        stop[v] += 1;
    } else{
        int tm = (tl + tr) / 2;
        stop[2 * v] += stop[v];
        stop[2 * v + 1] += stop[v];
        st[2 * v] += stop[v];
        st[2 * v + 1] += stop[v];
        stop[v] = 0;
        if (r <= tm){
            upd(2 * v, tl, tm, l, r);
        } else if (l > tm){
            upd(2 * v + 1, tm + 1, tr, l, r);
        } else{
            upd(2 * v, tl, tm, l, r);
            upd(2 * v + 1, tm + 1, tr, l, r);
        }
        st[v] = max(st[2 * v], st[2 * v + 1]);
    }
}

ll getVal(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r){
        return st[v];
    } else{
        int tm = (tl + tr) / 2;
        stop[2 * v] += stop[v];
        stop[2 * v + 1] += stop[v];
        st[2 * v] += stop[v];
        st[2 * v + 1] += stop[v];
        stop[v] = 0;
        if (r <= tm){
            return getVal(2 * v, tl, tm, l, r);
        }
        if (l > tm){
            return getVal(2 * v + 1, tm + 1, tr, l, r);
        }
        return max(getVal(2 * v, tl, tm, l, r), getVal(2 * v + 1, tm + 1, tr, l, r));
    }
}

int main()
{
    ll n, q;
    cin >> n >> q;
    g.assign(n, vector<ll>());
    p.assign(n, 0);
    pos.assign(n, 0);
    h.assign(n, -1);
    sz.assign(n, 0);
    tin.assign(n, 0);
    for (int i = 0; i < n - 1; ++i){
        ll pp;
        cin >> pp;
        pp--;
        g[pp].push_back(i + 1);
        p[i + 1] = pp;
    }
    s.resize(n);
    for (int i = 0; i < n; ++i){
        cin >> s[i];
    }
    bfs(0);
    //cout << "bfs done" << endl;
    dfs1(0);
    dfs2(0, 0);
    vector<ll> ans(n);
    st.assign(4 * n, 0);
    stop.assign(4 * n, 0);
    for (int i = 0; i < n; ++i){
        int x = a[i];
        ll d = 0;
        if (tin[x] + 1 <= n - 1){
            d = max(d, getVal(1, 0, n - 1, tin[x] + 1, n - 1));
            //cout << "val: " << tin[x] + 1 << " " << n - 1 << "; " << d << endl;
        }
        //cout << "working: " << x << endl;
        while (x != 0){
            if (h[x] == x){
                //cout << "upd st " << tin[x] << " " << tin[x] << endl;
                //cout << "upd check: " << getVal(1, 0, n - 1, tin[x], tin[x]) << endl;
                upd(1, 0, n - 1, tin[x], tin[x]);
                if (tin[p[x]] + 1 <= tin[x] - 1){
                    d = max(d, getVal(1, 0, n - 1, tin[p[x]] + 1, tin[x] - 1));
                    //cout << "val: " << tin[p[x]] + 1 << " " << tin[x] - 1 << "; " << d << endl;
                }
                x = p[x];
            } else{
                //cout << "upd st " << tin[h[x]] + 1 << " " << tin[x] << endl;
                upd(1, 0, n - 1, tin[h[x]] + 1, tin[x]);
                x = h[x];
            }
            if (x == 0){
                upd(1, 0, n - 1, tin[x], tin[x]);
            }
            //cout << x << endl;
        }
        //cout << "finished" << endl;
        //cout << d << endl;
        ans[i] = i - d;
    }
    for (int i = 0; i < q; ++i){
        int vk;
        cin >> vk;
        vk--;
        cout << ans[pos[vk]] << endl;
    }
    return 0;
}
*/
