#include<cstdio>
#include<cctype>
#include<vector>

#define maxn 666

const int inf=1e9;
const long long INF=1e18;

template<class T>

inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
	return f?-r:r;
}

template<class T>

inline T min(T a,T b){
	return a<b?a:b;
}

template<class T>

inline T max(T a,T b){
	return a>b?a:b;
}

template<class Tmp,int MAXN,int MAXM,Tmp INF>

struct MF{

	struct E{
		int v;
		Tmp c;
		int nxt;
		E() {}
		E(int v,Tmp c,int nxt):v(v),c(c),nxt(nxt) {}
	}e[MAXM<<1];

	int n,s,t,hd,tl,s_e,head[MAXN],cur[MAXN],lev[MAXN],q[MAXN];

	inline void a_e(int u,int v,Tmp c){
		e[++s_e]=E(v,c,head[u]);
		head[u]=s_e;
	}

	inline void add(int u,int v,Tmp c){
		a_e(u,v,c),a_e(v,u,0);
	}

	inline void init(int N,int S,int T){
		n=N,s=S,t=T,s_e=1;
		for(int i=1;i<=n;i++)head[i]=0;
	}

	bool bfs(){
		for(int i=1;i<=n;i++)
			lev[i]=0,cur[i]=head[i];
		hd=0,tl=1,q[++tl]=s,lev[s]=1;
	    while(hd^tl){
			int u=q[++hd];
			for(int i=head[u];i;i=e[i].nxt){
				int v=e[i].v;
				if(!e[i].c||lev[v])continue;
				lev[v]=lev[u]+1,q[++tl]=v;
				if(v==t)return true;
			}
		}
		return false;
	}

	Tmp dfs(int u,Tmp f){
		if(u==t)return f;
		int d=0,used=0;
		for(int &i=cur[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(!e[i].c||lev[v]!=lev[u]+1)continue;
			if(!(d=dfs(v,min(f-used,e[i].c))))continue;
			e[i].c-=d,e[i^1].c+=d,used+=d;
			if(used==f)break;
		}
		if(!used)lev[u]=0;
		return used;
	}

	inline Tmp solve(){
	    Tmp flow=0;
		while(bfs())
		    flow+=dfs(s,INF);
		return flow;
	}

};

MF<int,maxn<<2,maxn<<4,inf> mf;

int K,n,m,t,cnt[11],l[maxn],r[maxn],f[maxn],size[maxn];

int p[maxn<<2],q[maxn<<2],b[maxn<<2];

std::vector<std::pair<int,int> > hull;

int find(int x){
	return x^f[x]?f[x]=find(f[x]):x;
}

#define x first
#define y second

template<class T>

void solve(T a,T b){
	int X=a.y-b.y;
	int Y=b.x-a.x;
	int s=2*n+1,t=s+1;
	mf.init(t,s,t);
	for(int i=1;i<=n;i++){
		if(l[i]<2||r[i]>K-1||f[i]!=i)continue;
		mf.add(s,i,l[i]==2?Y*size[i]:inf);
		if(K==5)mf.add(i,i+n,l[i]<=3&&r[i]>=3?(X+Y)*size[i]:inf);
		mf.add(i+n,t,r[i]==4?X*size[i]:inf);
	}
	for(int i=1;i<=m;i++){
		int u=find(p[i]);
		int v=find(q[i]);
		if(::b[i]>1||u==v)continue;
		mf.add(u+n,v,inf),mf.add(v+n,u,inf);
	}
	mf.solve();
	T c={0,0};
	for(int i=1;i<=n;i++){
		if(l[i]<2||r[i]>K-1||f[i]!=i)continue;
		if(!mf.lev[i])c.x+=size[i];
		if(mf.lev[i+n])c.y+=size[i];
	}
	if(!((c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y)))return;
	hull.push_back(c),solve(a,c),solve(c,b);
}

#undef x
#undef y

inline void query(){
	long long ans=-INF;
	static long long val[11];
	for(int i=2;i<K;i++)
		val[i]=read<long long>();
	for(auto P:hull){
		cnt[2]=P.first,cnt[K-1]=P.second;
		if(K==5)cnt[3]=n-cnt[1]-cnt[2]-cnt[4]-cnt[5];
		long long s=0,sum=0;
		for(int i=1;i<=K;i++){
			s+=cnt[i]*(cnt[i]+cnt[i+1]*2);
			sum+=cnt[i]*val[i];
		}
		sum+=s*1000000;
		ans=max(ans,sum);
	}
	printf("%lld\n",ans);
}

inline void work(){
	K=read<int>();
	n=read<int>();
	m=read<int>();
	int t=read<int>();
	for(int i=1;i<=K;i++)cnt[i]=0;
	for(int i=1;i<=n;i++){
		l[i]=read<int>();
		r[i]=read<int>();
	}
	for(int i=1;i<=m;i++){
		p[i]=read<int>();
		q[i]=read<int>();
		b[i]=read<int>();
	}
	for(int T=1;T<=n;T++)
		for(int i=1;i<=m;i++){
			int x=p[i],y=q[i],w=b[i];
			l[x]=max(l[x],l[y]-w),l[y]=max(l[y],l[x]-w);
			r[x]=min(r[x],r[y]+w),r[y]=min(r[y],r[x]+w);
		}
	int mxl=0,mxr=0;
	for(int i=1;i<=n;i++){
		if(r[i]>1&&l[i]<K)
			l[i]=max(l[i],2),r[i]=min(r[i],K-1);
		if(l[i]==r[i])cnt[l[i]]++;
		mxl+=(l[i]==2),mxr+=(r[i]==K-1);
	}
	for(int i=1;i<=n;i++)
	    f[i]=i,size[i]=0;
	for(int i=1;i<=m;i++)
		if(!b[i])f[find(p[i])]=find(q[i]);
	for(int i=1;i<=n;i++)size[find(i)]++;
	hull={{cnt[2],cnt[K-1]},{cnt[2],mxr},{mxl,cnt[K-1]}};
	if(K==5)solve(hull[1],hull[2]);
	while(t--)query();
}

int main(){
	read<int>();
	int t=read<int>();
	while(t--)work();
	return 0;
}