3D 프린팅

3D 프린팅으로 정육면체를 이어 붙인 설치 미술 작품을 만들어 Installation art Contest with Printed Cubes(ICPC)에 출품하려고 한다. 작품은 크기가 같고 방향도 같은 정육면체 정확히 $k$개로 이루어진다.

먼저 CAD로 3차원 공간에 정육면체를 놓을 후보 위치 $n$개를 잡는다($n \ge k$). 후보 위치 전부에 정육면체를 놓으면 다음 세 조건이 성립한다.

• 정육면체 하나가 겹치는 다른 정육면체의 개수는 0개, 1개, 2개 중 하나다. 3개 이상과 겹치지는 않는다.
• 정육면체 하나가 다른 두 정육면체와 겹치면, 그 두 정육면체는 서로 겹치지 않는다.
• 서로 겹치지 않는 두 정육면체는 면에서도 모서리에서도 꼭짓점에서도 닿지 않는다.

이제 후보 $n$개 중 서로 다른 위치 $k$개를 골라 정육면체를 놓는다. 이때 정육면체 $k$개의 합집합은 연결된 다면체여야 한다. 3D 프린터는 보통 물체의 얇은 겉면만 출력하므로, 필라멘트를 아끼려면 겉넓이가 가장 작은 다면체를 골라야 한다.

후보 $n$개 중 $k$개를 골라 만들 수 있는 연결된 다면체 가운데 겉넓이가 가장 작은 것의 겉넓이를 구하라.

그림 1. 같은 정육면체를 이어 붙여 만든 다면체.

입력은 여러 개의 데이터 집합으로 이루어진다. 데이터 집합은 최대 100개다. 각 데이터 집합의 형식은 다음과 같다.

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

첫 줄의 $n$은 후보 위치의 개수, $k$는 연결된 다면체를 이룰 정육면체의 개수, $s$는 정육면체 한 변의 길이다. $n$, $k$, $s$는 공백으로 구분한 정수다. 이어지는 $n$개의 줄은 후보 위치 $n$개를 나타낸다. $i$번째 줄의 정수 $x_i$, $y_i$, $z_i$는 그 위치에 정육면체를 놓았을 때 좌표가 가장 작은 꼭짓점의 좌표이며, 공백으로 구분한다. 정육면체의 모서리는 세 좌표축 가운데 하나와 나란하다.

$1 \le k \le n \le 2000$, $3 \le s \le 100$, $-4 \times 10^7 \le x_i, y_i, z_i \le 4 \times 10^7$이다. 후보 위치는 위에 적은 세 조건을 항상 만족한다.

입력의 끝은 공백으로 구분한 0 세 개가 있는 줄이다.

각 데이터 집합마다 겉넓이가 가장 작은 연결된 다면체의 겉넓이를 정수 하나로 한 줄에 출력한다. 정육면체 $k$개로 연결된 다면체를 만들 수 없으면 -1을 출력한다.