3D Printing

You are designing an installation art piece made of cubes with 3D printing technology, to enter it in the Installation art Contest with Printed Cubes (ICPC). The piece is made of exactly $k$ cubes of the same size that face the same direction.

First, a CAD system prepares $n$ candidate positions in 3D space where a cube can be placed, with $n \ge k$. When cubes are placed at every candidate position, the following three conditions hold.

• The number of other cubes that one cube overlaps is 0, 1, or 2. No cube overlaps three or more.
• When one cube overlaps two other cubes, those two cubes do not overlap each other.
• Two cubes that do not overlap touch neither at a face, nor at an edge, nor at a corner.

Now choose $k$ different positions among the $n$ candidates and place a cube at each of them. The union of the $k$ cubes must be a connected polyhedron. A 3D printer usually prints only the thin surface of an object, so the piece that saves filament is the one with the smallest surface area.

Find the smallest surface area among the connected polyhedra that $k$ of the $n$ candidate positions can produce.

Figure 1. A polyhedron formed with connected identical cubes.

The input holds several datasets. There are at most 100 datasets. Each dataset has the following format.

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

On the first line of a dataset, $n$ is the number of candidate positions, $k$ is the number of cubes that form the connected polyhedron, and $s$ is the edge length of a cube. $n$, $k$, and $s$ are integers separated by a space. The next $n$ lines give the $n$ candidate positions. On the $i$-th line, the integers $x_i$, $y_i$, and $z_i$ are the coordinates of the corner with the smallest coordinate values of the cube placed there, separated by a space. The edges of a cube are parallel to one of the three coordinate axes.

The values satisfy $1 \le k \le n \le 2000$, $3 \le s \le 100$, and $-4 \times 10^7 \le x_i, y_i, z_i \le 4 \times 10^7$. The candidate positions always satisfy the three conditions above.

The end of the input is a line with three zeros separated by a space.

For each dataset, print the smallest surface area of the connected polyhedron as one integer on its own line. If no $k$ cubes form a connected polyhedron, print -1.