헤븐스 키친

남규는 입대를 기다리며 하루 종일 영상을 본다. 가장 즐겨 보는 프로그램은 요리 대결 방송인 헤븐스 키친이다. 이 방송에는 요리사 $N$명이 출연하고, 매일 그중 두 명이 요리 대결을 한 판 벌인다. 이긴 요리사는 천국으로 떠나고, 진 요리사는 남아서 다음 대결을 계속한다. 마지막까지 혼자 남은 요리사는 지옥으로 보내진다.

요리사에게는 1번부터 $N$번까지 번호가 붙어 있다. $i$번 요리사의 요리 실력은 $P_i$, 인기도는 $C_i$이다. 요리 실력이 같은 두 요리사는 없다.

그날의 시청률은 그날 대결하는 두 요리사만으로 정해진다. 요리사 $A$와 요리사 $B$가 대결하면 그날의 시청률은 $\left\lfloor \frac{C_A + C_B}{|P_A - P_B|} \right\rfloor$이다. $\lfloor x \rfloor$는 $x$보다 작거나 같은 가장 큰 정수이다.

대결의 승패는 요리 실력이나 인기도와 상관없이 정해진다. 어느 두 요리사가 맞붙을지도, 그중 누가 이길지도 마음대로 정할 수 있다.

대결 $N-1$번이 끝나면 요리사 한 명만 남는다. 대결 순서와 승패를 잘 정해서 $N-1$일 동안의 시청률의 합을 최대로 만들고, 그때의 대진을 출력하자.

첫째 줄에 요리사의 수 $N$이 주어진다. ($2 \le N \le 1000$)

이어지는 $N$개의 줄 중 $i$번째 줄에 $i$번 요리사의 요리 실력 $P_i$와 인기도 $C_i$가 공백을 사이에 두고 주어진다. ($0 \le P_i, C_i \le 10^9$, $i \ne j$이면 $P_i \ne P_j$)

첫째 줄에 시청률의 합의 최댓값을 출력한다.

둘째 줄부터 $N-1$개의 줄에 대결이 열리는 순서대로 진 요리사의 번호와 이긴 요리사의 번호를 공백을 사이에 두고 출력한다. 이긴 요리사가 천국으로 떠나고 진 요리사가 남는다는 점에 주의한다.

합이 최대가 되는 대진은 여럿일 수 있으므로, 다음 두 규칙으로 정해지는 대진 하나만 정답으로 인정한다.

첫째, 어느 두 요리사가 맞붙는지는 이렇게 정한다. 처음에 요리사 $N$명은 각자 자기 혼자인 그룹에 속한다. $i < j$인 모든 쌍 $(i, j)$를 그 둘이 대결할 때의 시청률이 큰 순서로 살펴본다. 시청률이 같으면 $i$가 작은 쌍을 먼저 보고, $i$도 같으면 $j$가 작은 쌍을 먼저 본다. 이 순서로 쌍을 하나씩 확인하면서 두 요리사가 서로 다른 그룹에 있으면 그 쌍을 대진에 넣고 두 그룹을 합친다. 같은 그룹이면 건너뛴다. 이렇게 하면 대결 $N-1$번이 정해진다.

둘째, 대결이 열리는 순서는 이렇게 정한다. 천국으로 떠나는 요리사에게 아직 치르지 않은 대결이 남아 있으면 안 되므로, 남은 대결이 정확히 하나인 요리사만 그 대결에서 이길 수 있다. 그런 요리사가 여럿이면 출력할 두 수를 (진 요리사, 이긴 요리사) 쌍으로 보고 사전순으로 가장 앞서는 대결을 먼저 연다.