Building Moon City

Science and technology have advanced enough that cities can now be built on the Moon. Because construction on the Moon is extremely expensive, when there are $N$ cities we want to build as few connecting roads as possible. Specifically, we want the roads to form a single cycle of size $N$ that visits every city exactly once.

For each pair of cities, the cost of building a (two-way) road between them is fixed. Building a road between city $i$ and city $j$ lets you travel in both directions with no extra construction. So far this is very similar to the Traveling Salesman Problem, but here there is an additional cost.

Every road must be built as a straight line segment whose endpoints are the two cities. If two different roads cross at a point that is not a city, one of them must detour around the other, which incurs an extra cost. If $k$ roads all cross at a single non-city point, the extra cost incurred at that point is $\dfrac{k(k-1)C}{2}$, where $C$ is a constant given in the input. No three cities are collinear.

Find the minimum total cost of building the roads so that the conditions are satisfied.

The input consists of several test cases. Each test case has the format below, and the end of the input is marked by 0 0 in place of a test case.

The first line of each test case contains two integers $N$ and $C$ ($2 < N < 9$, $0 < C \le 1{,}000{,}000$). $N$ is the number of cities and $C$ is the constant used for the crossing penalty.

The next $N$ lines give the coordinates of the cities. The $i$-th of these lines contains two integers $x_i$ and $y_i$, the coordinates of city $i$ ($-1{,}000 \le x_i, y_i \le 1{,}000$). No two cities share the same location.

The following $N$ lines give an $N \times N$ cost matrix. The $j$-th value on the $i$-th line, $c_{ij}$, is the cost of building a road from city $i$ to city $j$ ($0 < c_{ij} \le 10^6$, $c_{ij} = c_{ji}$, $c_{ii} = 0$).

For each test case, print the answer on one line using the following format.

(test case number). (answer)

The test case number starts at $1$ and increases by $1$.