#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cstdlib>
#include <queue>
#include <utility>
using namespace std;

typedef long long LL;

const LL INF = 1LL << 50;

struct hole;

vector<int> xs, ys;
vector<vector<hole>> vhls;
int szx, szy;

inline int encode(int x, int y){
	return x * szy + y;
}
inline void decode(int e, int &x, int &y){
	x = e / szy;
	y = e % szy;
}

struct robot{
	int x, y, z;
	robot(int x_, int y_, int z_)
	: x(x_), y(y_), z(z_) {
		xs.push_back(x);
		ys.push_back(y);
	}
};

struct hole{
	int xl, yl, xr, yr;

	hole(int u1, int v1, int u2, int v2, int s)
	: xl(u1), yl(v1), xr(u2), yr(v2)
	{
		xs.push_back(u1);
		xs.push_back(u2);
		ys.push_back(v1);
		ys.push_back(v2);

		if(s >= 0){
			if(u1 > 1){ xs.push_back(u1 - 1); }
			if(u2 < s){ xs.push_back(u2 + 1); }

			if(v1 > 1){ ys.push_back(v1 - 1); }
			if(v2 < s){ ys.push_back(v2 + 1); }
		}
	}

	bool in(int x, int y) const{
		return xl <= x && x <= xr && yl <= y && y <= yr;
	}

	void nearest(int x, int y, int &nx, int &ny) const{
		if(x < xl){ nx = xl; }
		else if(x > xr){ nx = xr; }
		else{ nx = x; }

		if(y < yl){ ny = yl; }
		else if(y > yr){ ny = yr; }
		else{ ny = y; }
	}
};

struct cmpfst{
	template <class T, class U>
	bool operator() (const pair<T,U> &p, const pair<T,U> &q) const{
		return p.first < q.first;
	}
};

void compress(const vector<int> &v, int &t){
	t = lower_bound(v.begin(), v.end(), t) - v.begin();
}

vector<LL> calc(const robot &rb){
	unordered_map<int,LL> mp1, mp2;
	mp1.emplace(encode(rb.x, rb.y), 0);

	int hg = vhls.size() - 1;
	for(int z = rb.z + 1; z <= hg; ++z){
		for(auto p : mp1){
			int x, y, nx, ny;
			decode(p.first, x, y);
			for(const auto &h : vhls[z]){
				h.nearest(x, y, nx, ny);
				LL &t = mp2.emplace(encode(nx, ny), INF).first->second;
				t = min(t, p.second + abs(xs[x] - xs[nx]) + abs(ys[y] - ys[ny]) + 100);
			}
		}
		mp1.swap(mp2);
		mp2.clear();
	}

	typedef pair<LL,int> pli;

	vector<LL> ret(szx * szy, INF);
	priority_queue<pli,vector<pli>,cmpfst> pq;
	for(auto p : mp1){
		ret[p.first] = p.second;
		pq.emplace(-p.second, p.first);
	}

	int dd[5] = {0, -1, 0, 1, 0};

	while(!pq.empty()){
		auto p = pq.top();
		pq.pop();
		if(ret[p.second] != -p.first){ continue; }
		int x, y;
		decode(p.second, x, y);
		for(int i = 0; i < 4; ++i){
			int nx = x + dd[i];
			int ny = y + dd[i + 1];
			if(nx < 0 || nx >= szx || ny < 0 || ny >= szy){ continue; }
			int e = encode(nx, ny);
			LL c = -p.first + abs(xs[x] - xs[nx]) + abs(ys[y] - ys[ny]);
			if(ret[e] > c){
				ret[e] = c;
				pq.emplace(-c, e);
			}
		}
	}

	return ret;
}

int main(){
	ios::sync_with_stdio(false);

	int n, m, k, s;

	vector<robot> rbs;
	rbs.reserve(100);

	while(cin >> n >> m >> k >> s){
		xs = ys = {1, s};

		rbs.clear();
		vhls.clear();
		vhls.resize(k + 1);

		for(int i = 0; i < n; ++i){
			int x, y, z;
			cin >> x >> y >> z;
			rbs.emplace_back(x, y, z);
		}
		for(int i = 0; i < m; ++i){
			int u1, v1, u2, v2, w;
			cin >> u1 >> v1 >> u2 >> v2 >> w;
			vhls[w].emplace_back(u1, v1, u2, v2, w == k ? s : -1);
		}

		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		sort(ys.begin(), ys.end());
		ys.erase(unique(ys.begin(), ys.end()), ys.end());
		szx = xs.size();
		szy = ys.size();

		for(auto &r : rbs){
			compress(xs, r.x);
			compress(ys, r.y);
		}
		for(auto &hls : vhls){
			for(auto &h : hls){
				compress(xs, h.xl);
				compress(xs, h.xr);
				compress(ys, h.yl);
				compress(ys, h.yr);
			}
		}

		vector<vector<LL>> tms;
		for(int i = 0; i < n; ++i){
			tms.emplace_back(calc(rbs[i]));
		}

		LL ans = INF;
		for(int x = 0; x < szx; ++x){
			for(int y = 0; y < szy; ++y){
				bool ok = true;
				for(const auto &h : vhls.back()){
					if(h.in(x, y)){
						ok = false;
						break;
					}
				}
				if(ok){
					int e = encode(x, y);
					LL sum = 0;
					for(int i = 0; i < n; ++i){
						sum += tms[i][e];
					}
					ans = min(ans, sum);
				}
			}
		}
		if(ans == INF){ ans = -1; }
		cout << ans << '\n';
	}
}

Measured memory_bytes: 41736