점 짝짓기

2차원 평면에 $N$ 개의 점이 주어진다. $N$은 짝수이다. 점들은 $1$번부터 $N$번까지 번호가 매겨져 있다. $i$번 점의 좌표는 $(x_i, y_i)$이다. 점들을 두 개씩 짝을 지어 $\frac{N}{2}$ 개의 쌍을 만들려고 한다. 두 점 $(x_i, y_i)$과 $(x_j, y_j)$가 짝이 되었을 때 이 쌍에 대한 점수는 $|x_i-x_j|+|y_i-y_j|$이다.

점수 총합이 가능한 최대가 되도록 점을 짝짓는 프로그램을 작성하라.

입력 형식

첫 줄에 점의 수를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 200\,000;$ $N$은 짝수)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 $i$번 점의 좌표를 나타내는 두 정수 $x_i$, $y_i$가 공백으로 구분되어 주어진다. ($-1\,000\,000\,000 \le x_i, y_i \le 1\,000\,000\,000$)

출력 형식

첫 줄에 점수 총합의 최댓값을 출력한다.

그다음 $\frac{N}{2}$ 개의 줄에 걸쳐 최대 점수 총합을 만드는 짝짓기 방법을 출력한다. 각 줄은 짝을 짓는 두 점의 번호를 공백으로 구분하여 출력한다.

만약 가능한 답이 여러 가지라면, 그중 아무거나 하나 출력한다.

예제

4
1 2
2 1
2 2
1 1

4
4 3
1 2

예제 설명

$4$번 점과 $3$번 점으로 쌍을 만들어 $2$점을 얻고, $1$번 점과 $2$번 점으로 쌍을 만들어 $2$점을 얻는다. 점수의 총합은 $4$점이다.

채점 방식

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

해설