문시티 건설

과학 기술이 발전하여 달에도 도시를 건설할 수 있게 되었다. 그러나 달에서의 건설 비용은 매우 높기 때문에, $N$개의 도시가 있을 때 도시들을 잇는 도로를 최대한 적게 짓고자 한다. 우리는 도로들이 모든 도시를 정확히 한 번씩 지나는 크기 $N$의 하나의 싸이클을 이루도록 만들려고 한다.

각 도시 쌍마다 두 도시를 잇는 (양방향) 도로를 건설하는 비용이 정해져 있다. 도시 $i$와 도시 $j$를 잇는 도로를 지으면 추가 건설 없이 양쪽 방향으로 모두 통행할 수 있다. 여기까지는 외판원 순회(TSP) 문제와 매우 비슷하지만, 이 문제에는 추가 비용이 있다.

모든 도로는 두 도시를 양 끝점으로 하는 선분의 형태로 지어야 한다. 도시가 아닌 어떤 지점에서 서로 다른 도로들이 교차하면 한쪽 도로가 다른 쪽을 우회해야 하므로 추가 비용이 발생한다. 도시가 아닌 한 지점에서 $k$개의 도로가 동시에 교차하면, 그 지점에서 드는 추가 비용은 $\dfrac{k(k-1)C}{2}$ 이다(여기서 $C$는 입력으로 주어지는 상수이다). 어떤 세 도시도 한 직선 위에 있지 않다.

조건을 만족하도록 도로를 건설하는 데 필요한 최소 총비용을 구하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 형식은 아래와 같으며, 입력의 끝에는 테스트 케이스 대신 0 0이 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $N$, $C$가 주어진다($2 < N < 9$, $0 < C \le 1{,}000{,}000$). $N$은 도시의 수, $C$는 교차 추가 비용에 사용되는 상수이다.

이어지는 $N$개의 줄에는 각 도시의 좌표가 주어진다. 이 중 $i$번째 줄에는 $i$번 도시의 좌표를 나타내는 두 정수 $x_i$, $y_i$가 주어진다($-1{,}000 \le x_i, y_i \le 1{,}000$). 어떤 두 도시도 같은 위치에 있지 않다.

그다음 $N$개의 줄에는 $N \times N$ 비용 행렬이 주어진다. $i$번째 줄의 $j$번째 값 $c_{ij}$는 도시 $i$에서 도시 $j$로 가는 도로를 짓는 비용이다($0 < c_{ij} \le 10^6$, $c_{ij} = c_{ji}$, $c_{ii} = 0$).

각 테스트 케이스마다 아래 형식에 맞추어 답을 한 줄에 출력한다.

(테스트 케이스 번호). (정답)

테스트 케이스 번호는 $1$부터 시작하여 $1$씩 증가한다.