#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';
	}
}
### Prompt

Please formulate a Cpp solution to the following problem:

Development of Small Flying Robots

<image>

You are developing small flying robots in your laboratory.

The laboratory is a box-shaped building with K levels, each numbered 1 through K from bottom to top. The floors of all levels are square-shaped with their edges precisely aligned east-west and north-south. Each floor is divided into R × R cells. We denote the cell on the z-th level in the x-th column from the west and the y-th row from the south as (x, y, z). (Here, x and y are one-based.) For each x, y, and z (z > 1), the cell (x, y, z) is located immediately above the cell (x, y, z − 1).

There are N robots flying in the laboratory, each numbered from 1 through N. Initially, the i-th robot is located at the cell (xi, yi, zi).

By your effort so far, you successfully implemented the feature to move each flying robot to any place that you planned. As the next step, you want to implement a new feature that gathers all the robots in some single cell with the lowest energy consumption, based on their current locations and the surrounding environment.

Floors of the level two and above have several holes. Holes are rectangular and their edges align with edges of the cells on the floors. There are M holes in the laboratory building, each numbered 1 through M. The j-th hole can be described by five integers u1j, v1j, u2j, v2j, and wj. The j-th hole extends over the cells (x, y, wj) where u1j ≤ x ≤ u2j and v1j ≤ y ≤ v2j.

Possible movements of robots and energy consumption involved are as follows.

* You can move a robot from one cell to an adjacent cell, toward one of north, south, east, or west. The robot consumes its energy by 1 for this move.
* If there is a hole to go through immediately above, you can move the robot upward by a single level. The robot consumes its energy by 100 for this move.



The robots never fall down even if there is a hole below. Note that you can move two or more robots to the same cell.

Now, you want to gather all the flying robots at a single cell in the K-th level where there is no hole on the floor, with the least energy consumption. Compute and output the minimum total energy required by the robots.

Input

The input consists of at most 32 datasets, each in the following format. Every value in the input is an integer.

> N
>  M K R
>  x1 y1 z1
>  ...
>  xN yN zN
>  u11 v11 u21 v21 w1
>  ...
>  u1M v1M u2M v2M wM
>

N is the number of robots in the laboratory (1 ≤ N ≤ 100). M is the number of holes (1 ≤ M ≤ 50), K is the number of levels (2 ≤ K ≤ 10), and R is the number of cells in one row and also one column on a single floor (3 ≤ R ≤ 1,000,000).

For each i, integers xi, yi, and zi represent the cell that the i-th robot initially located at (1 ≤ xi ≤ R, 1 ≤ yi ≤ R, 1 ≤ zi ≤ K). Further, for each j, integers u1j, v1j, u2j, v2j, and wj describe the position and the extent of the j-th hole (1 ≤ u1j ≤ u2j ≤ R, 1 ≤ v1j ≤ v2j ≤ R, 2 ≤ wj ≤ K).

The following are guaranteed.

* In each level higher than or equal to two, there exists at least one hole.
* In each level, there exists at least one cell not belonging to any holes.
* No two holes overlap. That is, each cell belongs to at most one hole.



Two or more robots can initially be located at the same cell. Also note that two neighboring cells may belong to different holes.

The end of the input is indicated by a line with a single zero.

Output

For each dataset, print the minimum total energy consumption in a single line.

Sample Input


2
1 2 8
1 1 1
8 8 1
3 3 3 3 2
3
3 2 3
1 1 2
1 1 2
1 1 2
1 1 1 1 2
1 2 1 2 2
2 1 2 1 2
2
2 3 100
100 50 1
1 50 3
100 1 100 100 3
1 1 1 100 2
5
6 7 60
11 11 1
11 51 1
51 11 1
51 51 1
31 31 1
11 11 51 51 2
11 11 51 51 3
11 11 51 51 4
11 11 51 51 5
18 1 54 42 6
1 43 59 60 7
5
6 4 9
5 5 3
1 1 1
1 9 1
9 1 1
9 9 1
3 3 7 7 4
4 4 6 6 2
1 1 2 2 3
1 8 2 9 3
8 1 9 2 3
8 8 9 9 3
5
10 5 50
3 40 1
29 13 2
39 28 1
50 50 1
25 30 5
3 5 10 10 2
11 11 14 14 2
15 15 20 23 2
40 40 41 50 2
1 49 3 50 2
30 30 50 50 3
1 1 10 10 4
1 30 1 50 5
20 30 20 50 5
40 30 40 50 5
15
2 2 1000000
514898 704203 1
743530 769450 1
202298 424059 1
803485 898125 1
271735 512227 1
442644 980009 1
444735 799591 1
474132 623298 1
67459 184056 1
467347 302466 1
477265 160425 2
425470 102631 2
547058 210758 2
52246 779950 2
291896 907904 2
480318 350180 768473 486661 2
776214 135749 872708 799857 2
0


Output for the Sample Input


216
6
497
3181
1365
1930
6485356






Example

Input

2
1 2 8
1 1 1
8 8 1
3 3 3 3 2
3
3 2 3
1 1 2
1 1 2
1 1 2
1 1 1 1 2
1 2 1 2 2
2 1 2 1 2
2
2 3 100
100 50 1
1 50 3
100 1 100 100 3
1 1 1 100 2
5
6 7 60
11 11 1
11 51 1
51 11 1
51 51 1
31 31 1
11 11 51 51 2
11 11 51 51 3
11 11 51 51 4
11 11 51 51 5
18 1 54 42 6
1 43 59 60 7
5
6 4 9
5 5 3
1 1 1
1 9 1
9 1 1
9 9 1
3 3 7 7 4
4 4 6 6 2
1 1 2 2 3
1 8 2 9 3
8 1 9 2 3
8 8 9 9 3
5
10 5 50
3 40 1
29 13 2
39 28 1
50 50 1
25 30 5
3 5 10 10 2
11 11 14 14 2
15 15 20 23 2
40 40 41 50 2
1 49 3 50 2
30 30 50 50 3
1 1 10 10 4
1 30 1 50 5
20 30 20 50 5
40 30 40 50 5
15
2 2 1000000
514898 704203 1
743530 769450 1
202298 424059 1
803485 898125 1
271735 512227 1
442644 980009 1
444735 799591 1
474132 623298 1
67459 184056 1
467347 302466 1
477265 160425 2
425470 102631 2
547058 210758 2
52246 779950 2
291896 907904 2
480318 350180 768473 486661 2
776214 135749 872708 799857 2
0


Output

216
6
497
3181
1365
1930
6485356

### Response

```cpp
#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';
	}
}
```