#include<bits/stdc++.h>
using namespace std;
int n, m, p, k, s, mp[15][15];
int can [15][15][15][15];
int vis[15][15];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
struct node {
	int x, y, key, step;
};
bool operator<(node a, node b) {
	return a.step > b.step;
}
vector<int>key[15][15];
int main() {
	cin >> n >> m >> p >> k;
	for (int i = 1; i <= k; i++) {
		int x1, y1, x2, y2, g;
		cin >> x1 >> y1 >> x2 >> y2 >> g;
		if (g == 0) g = INT_MAX;
		can[x1][y1][x2][y2] = g;
	}
	cin >> s;
	for (int i = 1; i <= s; i++) {
		int x, y, q;
		cin >> x >> y >> q;
		key[x][y].push_back(q);
	}
	priority_queue<node>q;
	q.push({1, 1, 0, 0});
	vis[1][1] = 0;
	int ans = INT_MAX;
	while (!q.empty()) {
		node now = q.top();
		q.pop();
		if (now.x == n && now.y == m) {
			ans = min(ans, vis[now.x][now.y]);
		}
		for (int i = 0; i < 4; i++) {
			int xx = now.x + dx[i];
			int yy = now.y + dy[i];
			if (xx >= 1 && xx <= n && yy >= 1 && yy <= m) {
				if (can[now.x][now.y][xx][yy] == INT_MAX || can[xx][yy][now.x][now.y] == INT_MAX) {
					continue;
				}
				for (int k = 0; k < key[xx][yy].size(); k++) {
					if (key[xx][yy][i]) {
						if (((1 << (key[xx][yy][i] - 1)) & now.key) != now.key) {
							now.key += key[xx][yy][i];
						}
					}
				}
				if (can[now.x][now.y][xx][yy] || can[xx][yy][now.x][now.y]) {
					if (can[now.x][now.y][xx][yy] && ((1 << (can[now.x][now.y][xx][yy] - 1)&now.key) == now.key) && vis[xx][yy] > now.step) {
						q.push({xx, yy, now.key, now.step + 1});
						vis[xx][yy] = now.step;
					} else if (can[xx][yy][now.x][now.y] && ((1 << (can[xx][yy][now.x][now.y] - 1)&now.key) == now.key) && vis[xx][yy] > now.step) {
						q.push({xx, yy, now.key, now.step + 1});
						vis[xx][yy] = now.step;
					}
				} else if (vis[xx][yy] > now.step) {
					q.push({xx, yy, now.key, now.step + 1});
					vis[xx][yy] = now.step + 1;
				}
			}
		}
	}
	if (ans == INT_MAX) {
		cout << -1;
	} else {
		cout << ans;
	}
	return 0;
}