0185 - 小型飛行ロボット開発

問題

あなたは研究所で小型飛行ロボットを開発している．

研究所は K 階建ての直方体状の建物であり，下の階から順に 1 から K の番号がついている． それぞれの階の床は各辺が東西方向または南北方向に対して平行な正方形であり， それらの床は R × R 個のセルに分割されている． z 階の，西から x 番目の列の南から y 番目にあるセルを (x, y, z) で表す（x, y は 1 始まりとする）． それぞれの x, y, z (z > 1) に対し，セル (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 で表される． j 番目の穴はセル (x, y, w_j) (u_1j ≤ x ≤ u_2j, v_1j ≤ y ≤ v_2j) を含んでいる．

ロボットの可能な動きとそれに伴うエネルギー消費量は以下のとおりである．

• ロボットのいるセルから東西南北の 4 方向で隣り合うセルに移動することができる． この移動には 1 のエネルギーを消費する．
• もしロボットのいるセルの真上が穴に含まれているならば，ロボットを真上のセルに移動させることができる．この移動には 100 のエネルギーを消費する．

ロボットは，下に穴があっても落下することはないものとする． また，ふたつ以上のロボットを同じセルに移動させても良いものとする．

あなたはいま，飛んでいる全てのロボットを穴に含まれていない K 階のセルに最小のエネルギーで集めたい． ロボットの消費するエネルギーの合計値の最小値を計算し，出力せよ．

Input

入力は 32 個以下のデータセットからなる． 各データセットは次の形式で表される． 入力に現れる値は全て整数である．

N
M K R
x₁ y₁ z₁
...
x_N y_N z_N
u₁₁ v₁₁ u₂₁ v₂₁ w₁
...
u_1M v_1M u_2M v_2M w_M

N は研究所にあるロボットの個数 (1 ≤ N ≤ 100) である． M は穴の個数 (1 ≤ M ≤ 50)， K は研究所の階数 (2 ≤ K ≤ 10)， R は各階の 1 行及び 1 列のセルの個数 (3 ≤ R ≤ 1,000,000) である．

各 i に対し，x_i, y_i, z_i は i 番目のロボットが最初にいるセル (1 ≤ x_i ≤ R, 1 ≤ y_i ≤ R, 1 ≤ z_i ≤ K) を表す． また，各 j に対し， u_1j, v_1j, u_2j, v_2j, w_j は j 番目の穴の位置と範囲 (1 ≤ u_1j ≤ u_2j ≤ R, 1 ≤ v_1j ≤ v_2j ≤ R, 2 ≤ w_j ≤ K) を表す．

入力について以下のことが保証される．

• 2 階以上のどの階にも少なくともひとつは穴が存在する．
• どの階にも，穴に含まれないセルが少なくともひとつは存在する．
• どのふたつの穴の範囲も重ならない．すなわち，どのセルも高々ひとつの穴にしか含まれない．

二個以上のロボットが最初に同じ階の同じセルにいることはありうる． また，隣接するふたつのセルがそれぞれ異なる穴に含まれるということもありうる．

入力の終わりは，ひとつのゼロだけからなる行で表される．

Output

合計エネルギー消費の最小値を 1 行に出力せよ．

Sample Input/Output

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