도로망 건설

이차원 평면에 $N$ 개의 도시가 있다. $i$ 번째 도시의 위치는 $(X_i, Y_i)$이다. 모든 도시가 서로 연결되도록 도로망을 건설하려고 한다. 도로망은 도시, 추가된 거점 및 이들을 잇는 도로로 이루어진다.

도로망을 건설할 때 다음과 같은 규칙을 지켜야 한다:

• 거점은 평면 위의 점에 위치한다. 거점은 원하는 만큼 추가할 수 있다.
• 도로는 거점과 거점, 거점과 도시 혹은 도시와 도시를 잇는다. 단, 도로는 $x$축 혹은 $y$축에 평행해야 한다.

모든 도시가 서로 연결되어 있다는 것은 임의의 한 도시에서 도로를 통해 거점과 도시를 거쳐 다른 모든 도시에 갈 수 있음을 의미한다.

모든 도시가 서로 연결되도록 도로망을 건설하기 위해 필요한 도로 길이 총합을 최소화하는 프로그램을 작성하라.

입력 형식

첫 줄에 도시의 수를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 16$)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 도시의 위치를 나타내는 두 정수 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. ($1 \le X_i, Y_i \le 1\,000\,000\,000$)

서로 다른 두 도시가 같은 위치에 있는 경우는 주어지지 않는다.

출력 형식

첫 줄에 모든 도시가 서로 연결되도록 도로망을 건설하기 위해 필요한 도로 길이 총합의 최솟값을 출력한다.

그다음 줄에 도로망을 건설하기 위해 필요한 도로의 수 $M$을 출력한다. $(1 \le M \le 1\,000)$

$M$ 개의 줄에 걸쳐 도로망을 구성하는 도로에 대한 정보를 출력한다. 이중 $i$ 번째 줄에 네 정수 $a_i, b_i, c_i, d_i$를 공백으로 구분하여 출력한다. 이는 $i$ 번째 도로가 $(a_i, b_i)$에 있는 거점 혹은 도시와 $(c_i, d_i)$에 있는 거점 혹은 도시를 잇는다는 것을 의미한다. ($1 \le a_i, b_i, c_i, d_i \le 1\,000\,000\,000$; $(a_i, b_i) \ne (c_i, d_i)$; $a_i = c_i$ 또는 $b_i = d_i$)

가능한 모든 입력에 대해 출력 형식을 만족하는 도로망이 존재함을 증명할 수 있다.

예제

5
4 8
3 6
5 4
2 2
7 8

13
7
2 2 2 4
2 4 4 4
4 4 4 6
4 6 4 8
4 8 7 8
3 6 4 6
4 4 5 4

예제 설명

위 그림은 출력 예제의 답을 나타낸다. 검은색 원은 도시를 의미하고, 베이지색 원은 거점을 의미하고, 실선은 도로를 의미한다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

실제 도로망을 구성하여 출력하지 않고, 첫 줄에 최솟값만 출력하여 정답과 같으면 50%의 부분 점수를 받는다.

해설