#include <stdio.h>
#include <algorithm>

using namespace std;

#define nm 160
#define mm 1510
#define pm 8010
#define TMAX 3600

struct rec
{
	int x, y, z;
};

int comp(rec a, rec b)
{
	return a.y < b.y;
}

int n, m, k, p, c[TMAX][nm];
rec a[mm], b[pm];

int main()
{
	int i, j, crt, x, y;

	freopen("amenzi.in", "r", stdin);
    freopen("amenzi.out", "w", stdout);

    scanf("%d%d%d%d", &n, &m, &k, &p);

    for (i = 1; i <= m; ++i)
    	scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);

    for (i = 1; i <= k; ++i)
    	scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);

    sort(b + 1, b + k + 1, comp);

    for (i = 0; i <= 3500; ++i)
    	for (j = 1; j <= n; ++j)
        	c[i][j] = -1;

    c[0][1] = 0;

    for (crt = 1; crt <= k && b[crt].y == 0; ++crt)
    	c[0][1] += b[crt].z;

    for (i = 1; i <= 3500; ++i)
    {
    	for (j = 1; j <= n; ++j)
        	c[i][j] = c[i - 1][j];

    	for (j = 1; j <= m; ++j)
        {
        	if (i >= a[j].z && c[i - a[j].z][a[j].y] != -1 && (c[i][a[j].x] == -1 || c[i][a[j].x] < c[i - a[j].z][a[j].y]))
				c[i][a[j].x] = c[i - a[j].z][a[j].y];
                
        	if (i >= a[j].z && c[i - a[j].z][a[j].x] != -1 && (c[i][a[j].y] == -1 || c[i][a[j].y] < c[i - a[j].z][a[j].x]))
				c[i][a[j].y] = c[i - a[j].z][a[j].x];
        }

        for (; crt <= k && b[crt].y == i; ++crt)
        	if (c[i][b[crt].x] != -1)
	        	c[i][b[crt].x] += b[crt].z;
    }

    for (i = 1; i <= p; ++i)
    {
    	scanf("%d%d", &x, &y);

        printf("%d\n", c[y][x]);
    }

	return 0;
}