#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
const int N=3600;
const ll inf1=1e6,inf2=1e9,C=1e6;
struct E{
	int to,rev;
	ll flow;
};
int K,n,m,q,L[N+5],R[N+5],U[N+5],V[N+5],W[N+5],fa[N+5],sz[N+5];
int vst[N+5],dis[N+5],S,T,cur[N+5];
int gf(int x){
	return x==fa[x]?x:fa[x]=gf(fa[x]);
}
void Merge(int x,int y){
	x=gf(x),y=gf(y);
	if(x==y)return ;
	fa[x]=y,L[y]=max(L[y],L[x]),R[y]=min(R[y],R[x]),sz[y]+=sz[x];
}
vector<E> g[N+5];
void Add(int x,int y,ll z){
	g[x].push_back({y,g[y].size(),z});
	g[y].push_back({x,g[x].size()-1,0});
}
bool BFS(){
	queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	dis[T]=0,q.push(T);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(E i:g[x]){
			int y=i.to;
			if(!g[y][i.rev].flow)continue;
			if(dis[y]>dis[x]+1){
				dis[y]=dis[x]+1;
				q.push(y);
				if(y==S)return 1;
			}
		}
	}
	return 0;
}
ll DFS(int x,ll fl){
	if(!fl||x==T)return fl;
	ll ret=0;
	for(int &i=cur[x];i<g[x].size();i++){
		int y=g[x][i].to;
		if(!g[x][i].flow||dis[x]!=dis[y]+1)continue;
		ll dlt=DFS(y,min(fl,g[x][i].flow));
		fl-=dlt,ret+=dlt,g[x][i].flow-=dlt,g[y][g[x][i].rev].flow+=dlt;
		if(!fl)return ret;
	}
	return ret;
}
ll Dinic(){
	ll ret=0;
	while(BFS())memset(cur,0,sizeof(cur)),ret+=DFS(S,inf2);
	return ret;
}
vector<pr> conv;
void dfs(int x){
	vst[x]=1;
	for(E i:g[x])if(i.flow&&!vst[i.to])dfs(i.to);
}
void Build(pr lef,pr rht){
	if(lef==rht)return ;
	int x1=lef.first,y1=lef.second,x2=rht.first,y2=rht.second;
	//cerr<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<'\n';
	//assert(x1<=x2),assert(y1>=y2);
	S=n+n+1,T=n+n+2;
	for(int i=1;i<=n;i++){
		if(gf(i)!=i||!L[i])continue;
		ll v2=0,v4=0;
		if(L[i]==2)v2=sz[i]*(y1-y2);
		if(R[i]==4)v4=sz[i]*(x2-x1);
		Add(S,i,v4),Add(i,i+n,v2+v4),Add(i+n,T,v2),Add(i+n,i,inf1);
	}
	for(int i=1;i<=m;i++){
		int x=gf(U[i]),y=gf(V[i]);
		if(x==y||!L[x]||W[i]!=1)continue;
		Add(x+n,y,inf1),Add(y+n,x,inf1);
	}
	Dinic();
	//选 2 有 y1-y2 收益
	//选 4 有 x2-x1 收益 
	dfs(S);
	int x3=0,y3=0;
	for(int i=1;i<=n;i++){
		if(gf(i)!=i||!L[i])continue;
		if(vst[S]&&!vst[i]&&L[i]==2)x3+=sz[i];
		if(vst[i+n]&&!vst[T]&&R[i]==4)y3+=sz[i];
	}
	for(int i=1;i<=T;i++)g[i].clear(),vst[i]=0;
	if((y3-y1)*(x3-x2)==(y3-y2)*(x3-x1))return ;
	conv.push_back(pr(x3,y3));
	Build(lef,pr(x3,y3)),Build(pr(x3,y3),rht);
}
void Solve(){
	scanf("%d%d%d%d",&K,&n,&m,&q);
	for(int i=1;i<=n;i++)scanf("%d%d",&L[i],&R[i]),fa[i]=i,sz[i]=1;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&U[i],&V[i],&W[i]);
		if(!W[i])Merge(U[i],V[i]);
	}
	for(int cnt=1;cnt<=n;cnt++){
		for(int i=1;i<=m;i++){
			int x=gf(U[i]),y=gf(V[i]);
			if(!W[i]||x==y)continue;
			R[y]=min(R[y],R[x]+W[i]);
			L[y]=max(L[y],L[x]-W[i]);
			R[x]=min(R[x],R[y]+W[i]);
			L[x]=max(L[x],L[y]-W[i]);
		}
	}
	int mus[10]={0},mx2=0,mx4=0,all=0;
	for(int i=1;i<=n;i++){
		if(gf(i)!=i)continue;
		if(R[i]<=2)mus[R[i]]+=sz[i],L[i]=R[i]=0;
		else if(L[i]>=4)mus[L[i]]+=sz[i],L[i]=R[i]=0;
		else if(L[i]==R[i])mus[L[i]]+=sz[i],L[i]=R[i]=0;
		else {
			L[i]=max(L[i],2),R[i]=min(R[i],4);
			if(L[i]==2)mx2+=sz[i];
			if(R[i]==4)mx4+=sz[i];
			all+=sz[i];
		}
		//剩下的只会是 [2,3] [3,4] [2,3,4]
	}
	conv.push_back(pr(0,mx4));
	conv.push_back(pr(mx2,0));
	conv.push_back(pr(0,0));
	Build(pr(0,mx4),pr(mx2,0));
	for(int i=1;i<=q;i++){
		ll ans=0,v[10]={0};
		for(int j=2;j<K;j++)scanf("%lld",&v[j]);
		for(pr j:conv){
			int c2=j.first,c4=j.second,rl[10]={0};
			memcpy(rl,mus,sizeof(rl)),rl[2]+=c2,rl[4]+=c4,rl[3]+=all-c2-c4;
			ll sum=0;
			for(int k=2;k<K;k++)sum+=v[k]*rl[k];
			for(int k=1;k<=K;k++)
				for(int l=1;l<=K;l++)
					if(abs(k-l)<=1)sum+=C*rl[k]*rl[l];
			ans=max(ans,sum);
		}
		cout<<ans<<'\n';
	}
	for(int i=0;i<=max(m,2*n+2);i++)L[i]=R[i]=U[i]=V[i]=W[i]=fa[i]=sz[i]=vst[i]=0;
	conv.clear();
	//cerr<<"PP\n";
}
int main(){
	//freopen("qip5.in","r",stdin);
	//freopen("1.out","w",stdout);
	int t;
	scanf("%*d%d",&t);
	while(t--)Solve(); 
}