#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define ADD 100

struct LOC{
	LOC(){
		x = y = 0;
	}
	LOC(int arg_x,int arg_y){
		x = arg_x;
		y = arg_y;
	}
	void set(int arg_x,int arg_y){
		x = arg_x;
		y = arg_y;
	}
	bool operator<(const struct LOC &arg) const{
		if(x != arg.x){

			return x < arg.x;
		}else{

			return y < arg.y;
		}
	}
	bool operator==(const struct LOC &arg) const{
		return x == arg.x && y == arg.y;
	}

	int x,y;
};


struct Info{

	LOC loc;
	int floor;
};

struct Data{
	int x_1,y_1,x_2,y_2;
};

struct State{
	State(LOC arg_loc,int arg_sum_cost,int arg_hole_index){
		loc.set(arg_loc.x,arg_loc.y);
		sum_cost = arg_sum_cost;
		hole_index = arg_hole_index;
	}
	LOC loc;
	int sum_cost,hole_index;
};

int num_robot,num_hole,K,R;
Info info[105];
Data data[55];
vector<int> HOLE[10];
vector<State> V[105],dp[2];


int calc_dist(LOC a, LOC b){

	return abs(a.x-b.x)+abs(a.y-b.y);
}

LOC calc_near_loc(LOC loc,Data data){

	LOC ret;

	if(loc.y < data.y_1){

		if(loc.x < data.x_1){

			ret.set(data.x_1,data.y_1);

		}else if(loc.x > data.x_2){

			ret.set(data.x_2,data.y_1);

		}else{

			ret.set(loc.x,data.y_1);
		}


	}else if(loc.y > data.y_2){

		if(loc.x < data.x_1){

			ret.set(data.x_1,data.y_2);

		}else if(loc.x > data.x_2){

			ret.set(data.x_2,data.y_2);

		}else{

			ret.set(loc.x,data.y_2);
		}

	}else{

		if(loc.x < data.x_1){

			ret.set(data.x_1,loc.y);

		}else if(loc.x > data.x_2){

			ret.set(data.x_2,loc.y);

		}else{

			ret.set(loc.x,loc.y);
		}
	}

	return ret;
}


void func(){

	for(int i = 0; i < num_robot; i++){

		V[i].clear();
	}

	scanf("%d %d %d",&num_hole,&K,&R);

	for(int i = 0; i < K; i++){

		HOLE[i].clear();
	}

	for(int i = 0; i < num_robot; i++){

		scanf("%d %d %d",&info[i].loc.x,&info[i].loc.y,&info[i].floor);
		info[i].floor--;
	}

	int floor;

	for(int i = 0; i < num_hole; i++){

		scanf("%d %d %d %d %d",&data[i].x_1,&data[i].y_1,&data[i].x_2,&data[i].y_2,&floor);
		floor--;
		HOLE[floor].push_back(i);
	}

	LOC tmp,next_loc;
	int index,next_cost,data_index;
	int CURRENT = 0,NEXT = 1;
	bool FLG;

	for(int loop = 0; loop < num_robot; loop++){

		dp[CURRENT].clear();
		dp[NEXT].clear();

		tmp.set(info[loop].loc.x,info[loop].loc.y);

		index = -1;

		for(int k = 0; k < HOLE[info[loop].floor].size(); k++){
			data_index = HOLE[info[loop].floor][k];

			if(data[data_index].x_1 <= tmp.x && data[data_index].x_2 >= tmp.x &&
					data[data_index].y_1 <= tmp.y && data[data_index].y_2 >= tmp.y){
				index = data_index;
				break;
			}
		}
		dp[CURRENT].push_back(State(tmp,0,index));

		for(int next_floor = info[loop].floor+1; next_floor <= K-1; next_floor++){
			for(int i = 0; i < dp[CURRENT].size(); i++){

				tmp = dp[CURRENT][i].loc;

				for(int k = 0; k < HOLE[next_floor].size(); k++){
					next_loc = calc_near_loc(tmp,data[HOLE[next_floor][k]]);

					FLG = false;
					for(int a = 0; a < dp[NEXT].size(); a++){
						if(dp[NEXT][a].loc.x == next_loc.x && dp[NEXT][a].loc.y == next_loc.y){
							FLG = true;
							index = a;
							break;
						}
					}

					next_cost = dp[CURRENT][i].sum_cost+calc_dist(tmp,next_loc)+ADD;

					if(!FLG){ //初登場

						dp[NEXT].push_back(State(next_loc,next_cost,HOLE[next_floor][k]));

					}else{

						if(dp[NEXT][index].sum_cost > next_cost){
							dp[NEXT][index].sum_cost = next_cost;
						}
					}
				}
			}

			dp[CURRENT].clear();

			for(int a = 0; a < dp[NEXT].size(); a++){
				FLG = true;
				for(int b = 0; b < dp[NEXT].size(); b++){
					if(a == b)continue;
					 if(dp[NEXT][b].sum_cost+calc_dist(dp[NEXT][a].loc,dp[NEXT][b].loc) <= dp[NEXT][a].sum_cost){
						FLG = false;
						break;
					}
				}
				if(FLG){
					dp[CURRENT].push_back(dp[NEXT][a]);
				}
			}

			dp[NEXT].clear();
		}

		for(int k = 0; k < dp[CURRENT].size(); k++){

			V[loop].push_back(dp[CURRENT][k]);
		}
	}

	vector<int> X,Y;
	for(int i = 0; i < num_robot; i++){

		X.push_back(info[i].loc.x);
		Y.push_back(info[i].loc.y);
	}

	for(int i = 0; i < num_hole; i++){

		X.push_back(data[i].x_1);
		X.push_back(data[i].x_1-1);
		X.push_back(data[i].x_2);
		X.push_back(data[i].x_2+1);
		Y.push_back(data[i].y_1);
		Y.push_back(data[i].y_1-1);
		Y.push_back(data[i].y_2);
		Y.push_back(data[i].y_2+1);
	}

	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());

	sort(Y.begin(),Y.end());
	Y.erase(unique(Y.begin(),Y.end()),Y.end());

	vector<LOC> CANDIDATE;

	for(int i = 0; i < X.size(); i++){
		for(int k = 0; k < Y.size(); k++){
			CANDIDATE.push_back(LOC(X[i],Y[k]));
		}
	}

	vector<LOC> WORK = CANDIDATE;
	CANDIDATE.clear();

	for(int i = 0; i < WORK.size(); i++){
		FLG = true;
		for(int a = 0; a < HOLE[K-1].size(); a++){
			index = HOLE[K-1][a];
			if(data[index].x_1 <= WORK[i].x && data[index].x_2 >= WORK[i].x &&
					data[index].y_1 <= WORK[i].y && data[index].y_2 >= WORK[i].y){
				FLG = false;
				break;
			}
		}
		if(FLG){
			CANDIDATE.push_back(WORK[i]);
		}
	}

	int ans = BIG_NUM;
	int minimum,tmp_sum,tmp_cost;

	for(int i = 0; i < CANDIDATE.size(); i++){
		tmp_sum = 0;
		for(int a = 0; a < num_robot; a++){
			minimum = BIG_NUM;
			for(int k = 0; k < V[a].size(); k++){
				tmp_cost = V[a][k].sum_cost+calc_dist(V[a][k].loc,CANDIDATE[i]);
				minimum = min(minimum,tmp_cost);
			}
			tmp_sum += minimum;
		}
		ans = min(ans,tmp_sum);
	}

	printf("%d\n",ans);
}

int main(){

	while(true){

		scanf("%d",&num_robot);
		if(num_robot == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 4808