원판

2차원 평면에 $N$개의 원판이 있고, 그 중심은 모두 서로 다른 격자점 위에 있다. 이 원판들은 흥미로운 배치를 이루고 있는데, 서로 다른 두 원판 $A$와 $B$에 대해 $A$가 $B$ 안에 있거나 $B$가 $A$ 안에 있다(서로 접촉해도 된다). 각 원판의 모양은 원이다.

이제 원판은 잊고, 진실을 보자. 새로운 차원으로 발을 내디디면, $N$개의 중심점만 남은 놀랍고도 완전히 새로운 세계가 펼쳐진다. 더 나은 방식으로 원판을 재구성할 때가 되었다. 각 원판은 그 중심점 중 하나를 중심으로 해야 하고, 각 중심점은 정확히 하나의 원판의 중심이어야 한다. 서로 다른 두 원판은 모두 앞서 말한 배치를 만족해야 한다(즉, $A$가 $B$ 안에 있거나 $B$가 $A$ 안에 있다). 그리고 모든 원판의 반지름의 합이 최소이다. 원판의 반지름은 0일 수 있으며, 이것은 사실상 점이다.

$N$개의 서로 다른 격자점이 주어질 때, 이러한 원판의 반지름 합으로 가능한 최솟값을 구하시오. 절대 오차 또는 상대 오차가 $10^{-6}$ 미만이면 정답으로 인정된다.

입력의 첫 줄에 정수 $N$ ($2 \le N \le 16$)이 주어지며, 이는 중심점의 개수를 나타낸다. 다음 $N$개의 줄에 각각 두 정수 $x_i$ $y_i$ ($0 \le x_i, y_i \le 10^9$)가 주어지며, 좌표 $(x_i, y_i)$의 중심점을 나타낸다. 주어지는 중심점은 모두 서로 다르다고 가정해도 된다.

문제에서 주어진 조건을 만족하는 원판의 반지름 합으로 가능한 최솟값을 한 줄에 출력하시오.