소형 비행 로봇 개발

연구실에서 소형 비행 로봇을 개발하고 있다.

연구실은 층이 $K$개인 상자 모양 건물이고, 층에는 아래에서 위로 $1$번부터 $K$번까지 번호가 붙어 있다. 각 층의 바닥은 정사각형이고 변이 동서 방향과 남북 방향에 정확히 맞춰져 있으며, $R \times R$개의 칸으로 나뉘어 있다. $z$번째 층에서 서쪽으로부터 $x$번째 열, 남쪽으로부터 $y$번째 행에 있는 칸을 $(x, y, z)$로 쓴다. $x$와 $y$는 $1$부터 센다. $z > 1$인 모든 $x$, $y$, $z$에 대해 칸 $(x, y, z)$는 칸 $(x, y, z - 1)$ 바로 위에 있다.

연구실 안에는 로봇 $N$대가 날고 있고 $1$번부터 $N$번까지 번호가 붙어 있다. 처음에 $i$번 로봇은 칸 $(x_i, y_i, z_i)$에 있다.

로봇 한 대를 원하는 곳으로 옮기는 기능은 이미 완성했다. 다음 목표는 모든 로봇을 한 칸에 모으면서 에너지를 가장 적게 쓰는 것이다.

$2$층 이상인 층의 바닥에는 구멍이 여러 개 뚫려 있다. 구멍은 직사각형이고 변이 칸의 변과 맞닿아 있다. 건물에는 구멍이 $M$개 있고 $1$번부터 $M$번까지 번호가 붙어 있다. $j$번 구멍은 정수 다섯 개 $u_{1j}$, $v_{1j}$, $u_{2j}$, $v_{2j}$, $w_j$로 주어지며, $u_{1j} \le x \le u_{2j}$이고 $v_{1j} \le y \le v_{2j}$인 칸 $(x, y, w_j)$를 모두 덮는다.

로봇은 두 가지 방법으로 움직인다.

• 로봇을 북, 남, 동, 서 중 한 방향으로 인접한 칸에 옮길 수 있다. 이때 로봇은 에너지를 $1$ 쓴다.
• 로봇 바로 위에 지나갈 구멍이 있으면 그 구멍으로 로봇을 한 층 올릴 수 있다. 이때 로봇은 에너지를 $100$ 쓴다.

아래에 구멍이 있어도 로봇은 떨어지지 않는다. 로봇 두 대 이상을 같은 칸에 둘 수 있다.

바닥에 구멍이 없는 $K$층의 칸 하나에 로봇을 모두 모으려고 한다. 로봇들이 쓰는 총 에너지의 최솟값을 출력하라.

입력은 데이터 집합 최대 $32$개로 이루어지고, 각 데이터 집합의 형식은 다음과 같다. 입력의 모든 값은 정수이다.

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

$N$은 연구실에 있는 로봇의 수이다($1 \le N \le 100$). $M$은 구멍의 수이고($1 \le M \le 50$), $K$는 층의 수이며($2 \le K \le 10$), $R$은 한 층의 한 행과 한 열에 들어 있는 칸의 수이다($3 \le R \le 10^6$).

각 $i$에 대해 정수 $x_i$, $y_i$, $z_i$는 $i$번 로봇이 처음에 있는 칸을 나타낸다($1 \le x_i \le R$, $1 \le y_i \le R$, $1 \le z_i \le K$). 각 $j$에 대해 정수 $u_{1j}$, $v_{1j}$, $u_{2j}$, $v_{2j}$, $w_j$는 $j$번 구멍의 위치와 범위를 나타낸다($1 \le u_{1j} \le u_{2j} \le R$, $1 \le v_{1j} \le v_{2j} \le R$, $2 \le w_j \le K$).

다음이 보장된다.

• $2$층 이상인 각 층에는 구멍이 적어도 하나 있다.
• 각 층에는 어떤 구멍에도 속하지 않는 칸이 적어도 하나 있다.
• 두 구멍은 겹치지 않는다. 즉, 각 칸은 많아야 구멍 하나에 속한다.

로봇 두 대 이상이 같은 칸에서 시작할 수 있다. 이웃한 두 칸이 서로 다른 구멍에 속할 수도 있다.

입력의 끝은 $0$ 하나만 있는 줄로 나타낸다.

각 데이터 집합마다 최소 총 에너지 소모량을 한 줄에 출력한다.