#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <random>
#include <ctime>
#include <chrono>
#include <numeric>
#include <iomanip>
#include <cassert>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 610;
const ll W = 1e6;
const int INF = 1e9;

int K, n, m, q;
ll val[6];

typedef pair <int, int> seg;
#define lb first
#define rb second

seg a[MAXN];
inline void upd(seg &u, const seg &v) { u.lb = max(u.lb, v.lb), u.rb = min(u.rb, v.rb); }
int av[MAXN];

struct Cons
{
    int u, v, w;
}c[MAXN << 2];

int fa[MAXN], sz[MAXN];
int Find(int k) { return k == fa[k] ? k : fa[k] = Find(fa[k]); }
inline void Union(int u, int v)
{
    u = Find(u), v = Find(v);
    if (u == v) return;
    fa[v] = u, upd(a[u], a[v]), sz[u] += sz[v];
}

int st[MAXN], Vcnt[6], id[MAXN];
vector <seg> conv;
int ans[MAXN][7];

const int MAXE = 4010, MAXV = 1210;
int s, t;
struct Edge
{
    int v, nxt, c, f;
}e[MAXE << 1];
int head[MAXV], tot;
inline void AddEdge(int u, int v, int w)
{
    e[++tot] = Edge{v, head[u], w, 0}, head[u] = tot;
    e[++tot] = Edge{u, head[v], 0, 0}, head[v] = tot;
}
int lvl[MAXV], curh[MAXV];
inline bool BFS()
{
    memset(lvl, -1, sizeof(lvl));
    queue <int> q;
    lvl[s] = 0, q.push(s);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = head[u]; ~i; i = e[i].nxt)
        {
            int v = e[i].v;
            if (lvl[v] == -1 && e[i].c > e[i].f)
            {
                lvl[v] = lvl[u] + 1;
                if (v == t) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
int _DFS(int u, int cap)
{
    if (u == t || !cap) return cap;
    int flow = 0, sum;
    for (int &i = curh[u]; ~i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (lvl[v] == lvl[u] + 1 && e[i].c > e[i].f)
        {
            sum = _DFS(v, min(cap, e[i].c - e[i].f));
            if (!sum) { lvl[v] = -1; continue; }
            flow += sum, cap -= sum;
            e[i].f += sum, e[i ^ 1].f -= sum;
            if (!cap) break;
        }
    }
    return flow;
}
inline int Dinic()
{
    int flow = 0;
    while (BFS())
    {
        for (int i = 1; i <= t; i++) curh[i] = head[i];
        flow += _DFS(s, INF);
    }
    return flow;
}
int vis[MAXN];
void DFS(int u)
{
    vis[u] = 1;
    for (int i = head[u]; ~i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (!vis[v] && e[i].c > e[i].f) DFS(v);
    }
}

int X, Y;
inline void Solve(int x1, int y1, int x2, int y2)
{
    if (x1 == x2 && y1 == y2) return;
    int u = y1 - y2, v = x2 - x1, pos = 0;
    for (int i = 1; i <= n; i++)
        if (a[st[i]].lb == 2) e[pos].c = u * sz[st[i]], pos += 2;
    for (int i = 1; i <= n; i++)
        if (a[st[i]].rb == 4) e[pos].c = v * sz[st[i]], pos += 2;
    for (int i = 0; i <= tot; i++) e[i].f = 0;
    Dinic();
    for (int i = 1; i <= t; i++) vis[i] = 0;
    DFS(s);
    int x = X, y = Y;
    for (int i = 0; i <= tot; i++)
        if (e[i].c == e[i].f && vis[e[i ^ 1].v] && !vis[e[i].v])
        {
            if (e[i ^ 1].v == s) x -= sz[st[e[i].v]];
            if (e[i].v == t) y -= sz[st[e[i ^ 1].v - n]];
        }
    if ((x != x1 || y != y1) && (x != x2 || y != y2))
    {
        conv.emplace_back(x, y);
        if (x1 <= x && y1 >= y) Solve(x1, y1, x, y);
        if (x <= x2 && y >= y2) Solve(x, y, x2, y2);
    }
}

int main()
{
    // freopen("sample_C/ex_qip8.in", "r", stdin);
    // freopen("C.in", "r", stdin);
    // freopen("C.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    int Case, T;
    Read(Case), Read(T);
    while (T--)
    {
        Read(K), Read(n), Read(m), Read(q);
        for (int i = 1; i <= n; i++) Read(a[i].lb), Read(a[i].rb);
        for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
        for (int i = 1; i <= m; i++)
        {
            Read(c[i].u), Read(c[i].v), Read(c[i].w);
            if (c[i].w == 0) Union(c[i].u, c[i].v);
        }
        int top = 0;
        for (int i = 1; i <= n; i++)
            if (fa[i] == i) st[++top] = i;
        n = top;
        for (int i = 1; i <= m; i++) c[i].u = Find(c[i].u), c[i].v = Find(c[i].v);
        memset(Vcnt, 0, sizeof(Vcnt)), memset(val, 0, sizeof(val));
        for (int i = 1; i <= n; i++) av[st[i]] = 0;
        for (int i = 1; i <= n; i++)
            if (a[st[i]].rb != a[st[i]].lb && a[st[i]].rb != 1 && a[st[i]].lb != 5) upd(a[st[i]], seg(2, 4));
        int pre = 0;
        do
        {
            pre = n, top = 0;
            for (int i = 1; i <= n; i++)
                if (a[st[i]].lb == a[st[i]].rb) Vcnt[a[st[i]].lb] += sz[st[i]], av[st[i]] = a[st[i]].lb;
                else st[++top] = st[i];
            n = top;
            for (int i = 1; i <= m; i++)
            {
                if (c[i].w == 0) continue;
                if (av[c[i].u]) upd(a[c[i].v], seg(av[c[i].u] - c[i].w, av[c[i].u] + c[i].w));
                if (av[c[i].v]) upd(a[c[i].u], seg(av[c[i].v] - c[i].w, av[c[i].v] + c[i].w));
            }
        }
        while (n != pre);

        for (int i = 1; i <= n; i++) id[st[i]] = i;
        memset(head, -1, sizeof(head)), tot = -1;
        X = 0, Y = 0;
        s = n * 2 + 1, t = s + 1;
        for (int i = 1; i <= n; i++)
            if (a[st[i]].lb == 2) AddEdge(s, i, 0), X += sz[st[i]];
        for (int i = 1; i <= n; i++)
            if (a[st[i]].rb == 4) AddEdge(i + n, t, 0), Y += sz[st[i]];
        for (int i = 1; i <= m; i++)
            if (!av[c[i].u] && !av[c[i].v] && c[i].w == 1)
                AddEdge(id[c[i].u], id[c[i].v] + n, INF), AddEdge(id[c[i].v], id[c[i].u] + n, INF);
        for (int i = 1; i <= n; i++) AddEdge(i, i + n, INF);
        conv.clear(), conv.emplace_back(X, 0), conv.emplace_back(0, Y);
        Solve(0, Y, X, 0);

        int sum = 0;
        for (int i = 1; i <= n; i++) sum += sz[st[i]];
        for (int i = 0; i < conv.size(); i++)
        {
            for (int j = 1; j <= 5; j++) ans[i][j] = Vcnt[j];
            ans[i][2] += conv[i].lb, ans[i][3] += sum - conv[i].lb - conv[i].rb, ans[i][4] += conv[i].rb;
            ans[i][6] = 0;
            for (int j = 1; j <= 5; j++) ans[i][6] += ans[i][j] * ans[i][j];
            for (int j = 1; j < 5; j++) ans[i][6] += ans[i][j] * ans[i][j + 1] * 2;
        }
        int _ = conv.size();
        for (int i = 1; i <= 5; i++) ans[_][i] = Vcnt[i];
        ans[_][3] += sum, ans[_][6] = 0;
        for (int i = 1; i <= 5; i++) ans[_][6] += ans[_][i] * ans[_][i];
        for (int i = 1; i < 5; i++) ans[_][6] += ans[_][i] * ans[_][i + 1] * 2;

        while (q--)
        {
            for (int i = 2; i < K; i++) Read(val[i]);
            ll mx = 0, cur = 0;
            for (int i = 0; i <= conv.size(); i++)
            {
                cur = ans[i][6] * W;
                for (int j = 2; j <= 4; j++) cur += ans[i][j] * val[j];
                mx = max(mx, cur);
            }
            cout << mx << '\n';
        }
    }
    return 0;
}