#include<stdio.h>
#include<string.h>

int main()
{
	int n,m,k,p,i,sursa,dest,timp,mom,amend,nod;
	int cost[150][1500],ad[150][1500],amenzi[150][3501];	
	int best[150][3501],time,j;
	FILE *f=fopen("amenzi.in","r");
	FILE *g=fopen("amenzi.out","w");

	fscanf(f,"%i%i%i%i",&n,&m,&k,&p);
	for(i=0;i<m;i++)
	{
		fscanf(f,"%i%i%i",&sursa,&dest,&timp);
		cost[sursa-1][dest-1]=timp;
		ad[sursa-1][0]++;
		ad[sursa-1][ad[sursa-1][0]]=dest-1;
	}

	for(i=0;i<k;i++)
	{
		fscanf(f,"%i%i%i",&sursa,&mom,&amend);
		amenzi[sursa-1][mom]=amend;
	}

	

	memset(best,0,3501*150*sizeof(int));
	memset(amenzi,0,3501*150*sizeof(int));
	best[0][0]=amenzi[0][0];	

	
	for(i=1;i<=3500;i++)
	{
		for(j=0;j<n;j++)
		{
			for(k=1;k<=ad[j][0];k++)
			{
				nod=ad[j][k];
				if(i-cost[j][nod]>=0)
				{
					time=i-cost[j][nod];
					if(best[nod][time]+amenzi[j][i]>best[j][i])
						best[j][i]=best[nod][time]+amenzi[j][i];
				}
				
			}
			if(best[j][i-1]+amenzi[j][i]>best[j][i])
				best[j][i]=best[j][i-1]+amenzi[j][i];
			
		}
	}
	
	for(i=0;i<p;i++)
	{
		fscanf(f,"%i%i",&sursa,&mom);
		fprintf(g,"%i\n",best[sursa-1][mom]);
	}
	fclose(f);
	fclose(g);
	return 0;
}