005 - 3D プリント

立方体印刷によるインスタレーションコンテスト (Installation art Contest with Printed Cubes, ICPC) に出品するため， 我々は 3D プリンタを使って立方体を組み合わせたインスタレーションの作品をデザインしている． 今回はちょうど k 個の同じ大きさで同じ向きの立方体を用いて作品を作ることを試みている．

まず， CAD を用いて，立方体を配置する場所の候補となる場所を n (n ≥ k) 個 3D 空間中に用意する． 立方体を全ての候補場所に置いたとすると， 以下の 3 条件が満たされる．

• 各立方体は 0 個，1 個 または 2 個の立方体と重なることがあるが，3 個以上とは重ならない．
• ある立方体が 2 個の立方体と重なるとき，その 2 個の立方体は重ならない．
• 面や辺や頂点で接触するだけで重なりのない 2 個の立方体はない．

つぎに，この n 個の候補の中から k 個の異なる場所を上手に選び， そこに立方体を配置して， k 個の立方体の併合としてひとつの連結した多面体を得る． 3Dプリンタを用いるときは， 物体の薄い表面だけを印刷するのが普通である． プリンタ用の材料を節約するため， 最小の表面積を持つ多面体を見つけたい．

あなたの仕事は， 与えられた n 個の位置の中から選ばれた k 個の位置に置かれた k 個の連結する立方体が作る多面体のうち表面積が一番小さいものを探すことである．

図 E1. 連結した同じ大きさの立方体からなる多面体．

入力は複数のデータセットからなる． データセットの数は 100 以下である． 各データセットは次の形式で表される．

n k s
x1 y1 z1
... 
xn yn zn

1 行目の n は準備された場所の総数， k は求める多面体を構成する連結した立方体の個数， s は立方体の 1 辺の長さである． n, k, s はすべて整数であり．空白文字で区切られる． 続く n 行は立方体を配置しうる場所の座標を指定する． その i 行目には x_i, y_i, z_i の 3 個の整数があり， これらは立方体の頂点の中で座標値が最小のものを配置しうる座標を表す． 立方体の辺は座標軸のどれかと平行である． 座標値はすべて整数であり， 空白文字で区切られる． 配置場所に関する上述の 3 条件は満たされている．

各パラメタは以下の条件を満たす: 1 ≤ k ≤ n ≤ 2000, 3 ≤ s ≤ 100, -4×10⁷ ≤ x_i, y_i, z_i ≤ 4×10⁷.

入力の終わりは，空白で区切られた 3 個のゼロからなる行で表される．

各データセットについて， 表面積最小の連結した多面体の表面積を表す整数を 1 行に出力せよ． 連結した多面体を構成する k 個の立方体がない場合は -1 を出力せよ．

1 1 100
100 100 100
6 4 10
100 100 100
106 102 102
112 110 104
104 116 102
100 114 104
92 107 100
10 4 10
-100 101 100
-108 102 120
-116 103 100
-124 100 100
-132 99 100
-92 98 100
-84 100 140
-76 103 100
-68 102 100
-60 101 100
10 4 10
100 100 100
108 101 100
116 102 100
124 100 100
132 102 100
200 100 103
192 100 102
184 100 101
176 100 100
168 100 103
4 4 10
100 100 100
108 94 100
116 100 100
108 106 100
23 6 10
100 100 100
96 109 100
100 118 100
109 126 100
118 126 100
127 118 98
127 109 104
127 100 97
118 91 102
109 91 100
111 102 100
111 102 109
111 102 118
111 102 91
111 102 82
111 114 96
111 114 105
102 114 114
93 114 114
84 114 105
84 114 96
93 114 87
102 114 87
10 3 10
100 100 100
116 116 102
132 132 104
148 148 106
164 164 108
108 108 108
124 124 106
140 140 104
156 156 102
172 172 100
0 0 0

60000
1856
-1
1632
1856
2796
1640