문시티 건설

인류의 과학 기술이 발전하여 달에도 도시를 지을 수 있게 되었다. 하지만 여전히 달에 무언가를 짓는 것은 굉장히 값비싼 비용이 필요하므로, N개의 도시가 있을 때 도시 간의 도로를 가능한 한 조금 지으려고 한다. 우리는 도로들이 크기 N인 싸이클을 형성하도록 만들려고 한다.

각 도시 쌍마다 사이를 왕복하는 도로를 건설하는 데 비용이 정해져 있다. 또한, 도시 i에서 도시 j로 가는 도로를 건설하면 추가적인 건설 없이 도시 j에서도 도시 i로 갈 수 있다. 여기까지와는 외판원 순회 문제와 굉장히 유사하지만, 이 문제에서는 추가 비용이 있다. 도로를 지을 때 반드시 두 도시 사이를 양 끝점으로 하는 선분의 형태로 지어야 하는데, 도시가 아닌 곳에서 서로 다른 도로가 교차하게 되면 어느 한쪽이 다른 한쪽을 우회해 가야 하므로 추가 비용이 들어간다. 가령 도시가 아닌 어떤 한 지점에서 k개의 도로가 서로 교차한다면, 추가 비용은 총 k ∗ (k − 1) ∗ C/2 만큼 필요하다(C는 주어지는 상수). 어떤 세 도시도 한 직선 위에 있지 않다.

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

입력은 여러 개의 테스트 케이스로 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있으며, 입력의 끝에는 새 테스트 케이스 대신 0이 두 개 주어진다.

첫째 줄에 두 정수 N, C가 주어진다(2 < N < 9, 0 < C ≤ 1,000,000). N은 도시의 개수, C는 추가 비용과 관련된 상수이다.

이어서 N개의 줄에 각 도시의 위치가 주어진다. 이 중 i번째 줄에는 i번째 도시의 좌표를 의미하는 두 정수 xi, yi가 주어진다(−1,000 ≤ xi, yi ≤ 1,000). 어떤 두 도시도 같은 위치에 있지 않다.

이어서 N개의 줄에 N*N 행렬이 주어지는데 i행 j열 값 cij는 i번 도시에서 j번 도시로 가는 도로를 짓는 데 필요한 비용이다(0 < cij ≤ 106, cij = cji, cii = 0).

각 테스트 케이스마다 다음 양식을 지켜 정답을 출력한다.

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

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