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

#define int long long
const int _ = 603 , __ = 3003 , G = 1e6;
int C , K , N , M , Q , L[_] , R[_] , S[__] , T[__] , X[__] , cnt[6] , V[6] , sz[_] , bel[_]; 
vector < int > id[_];

int calc(){
	int sum = 0; for(int i = 2 ; i <= K - 1 ; ++i) sum += V[i] * cnt[i];
	for(int i = 1 ; i <= K ; ++i) for(int j = 1 ; j <= K ; ++j) if(abs(i - j) <= 1) sum += G * cnt[i] * cnt[j];
	return sum;
}

struct pii{
	int x , y; pii(int _x = 0 , int _y = 0):x(_x) , y(_y){}
	friend pii operator -(pii p , pii q){return pii(p.x - q.x , p.y - q.y);}
	pii rot(){return pii(y, -x);}
	friend int operator %(pii p , pii q){return p.x * q.y - p.y * q.x;}
}; vector < pii > hull; vector < vector < int > > hull_val;

const int MAX = 5e4 + 7; struct Edge{int end , upEd , f;}Ed[MAX];
int head[__] , cur[__] , dep[__] , cntEd , tar; queue < int > q;
void init(int t){tar = t; memset(head , 0 , sizeof(int) * (tar + 1)); cntEd = 1;}
void addEd(int x , int y , int c){Ed[++cntEd] = (Edge){y , head[x] , c}; head[x] = cntEd;}
void addE(int x , int y , int c){addEd(x , y , c); addEd(y , x , 0);}

bool bfs(){
	memset(dep , 0 , sizeof(int) * (tar + 1)); memcpy(cur , head , sizeof(int) * (tar + 1)); while(!q.empty()) q.pop();
	q.push(0); dep[0] = 1;
	while(!q.empty()){
		int t = q.front(); q.pop();
		for(int i = head[t] ; i ; i = Ed[i].upEd)
			if(Ed[i].f && !dep[Ed[i].end]){dep[Ed[i].end] = dep[t] + 1; q.push(Ed[i].end); if(Ed[i].end == tar) return 1;}
	}
	return 0;
}

int dfs(int x , int v){
	if(x == tar) return v;
	int sum = 0;
	for(int &i = cur[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].f && dep[Ed[i].end] == dep[x] + 1){
			int f = dfs(Ed[i].end , min(Ed[i].f , v - sum)); sum += f; Ed[i].f -= f; Ed[i ^ 1].f += f;
			if(sum == v) break;
		}
	return sum;
}

pii dinic(){
	while(bfs()) dfs(0 , 1e15);
	pii ans;
	for(int i = 1 ; i <= N ; ++i)
		if(L[i] >= 2 && R[i] <= 4 && ~sz[i])
			if(!dep[i]) ans.x += sz[i];
			else if(dep[i + N]) ans.y += sz[i];
	return ans;
}

void hull_div(pii hL , pii hR){
	pii dir = (hL - hR).rot(); init(2 * N + 1);
	for(int i = 1 ; i <= N ; ++i)
		if(L[i] >= 2 && R[i] <= 4 && ~sz[i]){
			addE(0 , i , L[i] >= 3 ? 1e9 : dir.y * sz[i]);
			addE(i , N + i , L[i] == 4 || R[i] == 2 ? 1e9 : (dir.x + dir.y) * sz[i]);
			addE(N + i , tar , R[i] <= 3 ? 1e9 : dir.x * sz[i]);
		}
	for(int i = 1 ; i <= M ; ++i){
		int x = bel[S[i]] , y = bel[T[i]];
		if(x != y && ~sz[x] && ~sz[y] && X[i] == 1){
			addE(x + N , y , 1e9); addE(y + N , x , 1e9);
		}
	}
	pii mid = dinic(); if((hR - mid) % (hL - mid)){hull.push_back(mid); hull_div(hL , mid); hull_div(mid , hR);}
}

void hull_prepare(){
	hull.clear(); hull.push_back(pii(cnt[2] , cnt[4]));
	int num2 = 0 , num4 = 0; for(int i = 1 ; i <= N ; ++i){num2 += L[i] == 2; num4 += R[i] == 4;}
	hull.push_back(pii(num2 , cnt[4])); hull.push_back(pii(cnt[2] , num4)); hull_div(hull[2] , hull[1]);
	memset(V , 0 , sizeof(V)); hull_val.clear();
	for(auto t : hull){
		cnt[2] = t.x; cnt[4] = t.y; cnt[3] = N - t.x - t.y - cnt[1] - cnt[5];
		hull_val.push_back({calc() , cnt[2] , cnt[3] , cnt[4]});
	}
}

signed main(){
	//freopen("qip.in","r",stdin); freopen("qip.out","w",stdout); freopen("qip.log","w",stderr);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(cin >> C >> C ; C ; --C){
		memset(cnt , 0 , sizeof(cnt)); cin >> K >> N >> M >> Q; for(int i = 1 ; i <= N ; ++i){cin >> L[i] >> R[i]; sz[i] = 0; id[i].clear();}
		for(int i = 1 ; i <= M ; ++i){cin >> S[i] >> T[i] >> X[i]; id[S[i]].push_back(i); id[T[i]].push_back(i);}
		for(int i = 1 ; i <= N ; ++i) for(int j = 1 ; j <= N ; ++j) for(auto p : id[j]){int x = S[p] + T[p] - j; L[x] = max(L[x] , L[j] - X[p]); R[x] = min(R[x] , R[j] + X[p]);}
		for(int i = 1 ; i <= N ; ++i){if(R[i] != 1 && L[i] != K){L[i] = max(L[i] , 2ll); R[i] = min(R[i] , K - 1);} if(L[i] == R[i]) ++cnt[L[i]]; else ++cnt[0];}
		if(K == 5){
			for(int i = 1 ; i <= N ; ++i)
				if(~sz[i]){
					int cnt = 0; queue < int > q; q.push(i); sz[i] = -1;
					while(!q.empty()){
						int t = q.front(); q.pop(); ++cnt; bel[t] = i;
						for(auto p : id[t]){int x = S[p] + T[p] - t; if(X[p] == 0 && ~sz[x]){sz[x] = -1; q.push(x);}}
					}
					sz[i] = cnt;
				}
			hull_prepare();
		}
		while(Q--){
			for(int i = 2 ; i <= K - 1 ; ++i) cin >> V[i];
			switch(K){
			case 3: cout << calc() << '\n'; break;
			case 4:
				static int V2 , V3;
				cnt[2] += cnt[0]; V2 = calc(); cnt[2] -= cnt[0];
				cnt[3] += cnt[0]; V3 = calc(); cnt[3] -= cnt[0];
				cout << max(V2 , V3) << '\n'; break;
			case 5:
				static int mxans; mxans = 0;
				for(auto t : hull_val) mxans = max(mxans , t[0] + t[1] * V[2] + t[2] * V[3] + t[3] * V[4]);
				cout << mxans << '\n';
			}
		}
	}
	return 0;
}