영업 사원의 순회 경로

Weight For It 회사는 여러 주에 있는 고객에게 홈짐 장비를 판매한다. 각 주의 영업 사원은 현재 3명에서 8명의 고객으로 이루어진 특정 구역을 담당하고 있다. 각 영업 사원은 하루에 담당 고객을 모두 방문하는 최단 경로를 계산해 두었다. 이를 영업 순회 경로라고 한다.

Weight For It의 매출이 줄어들자 회사는 영업 사원 수를 절반으로 줄이고, 해고된 절반의 구역을 한 주에 남은 절반의 사원에게 하나씩 재배정하기로 했다. 공정성을 위해 남은 각 영업 사원에게는 해고된 사원의 구역이 정확히 하나씩 배정된다. 배정이 끝나면 남은 영업 사원은 최소 영업 순회 경로를 다시 계산해야 하고, 비용을 더 줄이기 위해 Weight For It는 새 영업 순회 경로 전체 길이의 합이 최소가 되도록 구역을 배정하려 한다.

예를 들어, 왼쪽의 그림 I.1은 한 주에 있는 네 구역의 배치를 보여준다. 구역 A와 B의 영업 사원이 해고되었다고 하자. 그러면 이 구역들을 재배정하는 최선의 방법은 구역 A의 고객 6명을 구역 C의 영업 사원에게, 구역 B의 고객 4명을 구역 D의 영업 사원에게 배정하는 것이다. 새 구역 C'과 D' 각각의 최단 영업 순회 경로는 오른쪽에 나와 있다.

그림 I.1: (a) 해고 전 네 구역. (b) 해고 후 두 구역. 이 예는 샘플 입력 1에 해당한다.

입력은 구역의 수를 나타내는 양의 짝수 정수 d (d ≤ 50)로 시작한다. 다음 d개 줄에는 각 구역의 고객 수와 위치가 구역 1부터 순서대로 한 줄에 하나씩 주어진다. 각 줄은 구역의 고객 수를 나타내는 정수 n (3 ≤ n ≤ 8)으로 시작하고, 이어서 고객의 위치를 나타내는 n개의 정수 좌표쌍 x y (−10 000 ≤ x, y ≤ 10 000)가 주어진다. 처음 나열된 d/2개 구역은 해고된 영업 사원의 구역이다. 두 고객 사이의 거리는 유클리드 거리이며, 모든 고객의 위치는 서로 다르다.

해고 전 모든 영업 순회 경로 길이의 합과 해고 후 모든 영업 순회 경로 길이의 합을 차례로 출력한다. 답의 절대 오차는 10−2 이내여야 한다.