14574번 - 헤븐스 키친 스페셜 저지

문제

남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 한 명이 천국으로 떠난다.

만일 한 명의 요리사가 남는다면 해당 요리사는 지옥으로 보내진다.

이 프로그램에 출연하는 N명의 요리사는 각각 요리 실력 P_i와 인기도 C_i를 갖고 있다.

이 프로그램의 시청률은 그 날 요리 대결을 펼치는 두 요리사의 요리 실력과 인기도에 의해 결정된다.

만일 요리사 A와 요리사 B가 대결을 펼친다면, 그 날의 시청률은 $ floor \left( \frac{C_A + C_B}{|P_A - P_B|} \right) $로 결정된다. 어떤 두 요리사의 요리 실력이 같은 경우는 없다.

(floor(x)는 x보다 작거나 같은 가장 큰 정수)

대결의 승패는 요리 실력이나 인기도와는 관계없이 결정될 수 있다.

남규는 이 프로그램을 시청하던 중, 요리사들의 대결 순서와 승패에 따라 프로그램의 시청률이 크게 달라질 수도 있다는 사실을 발견했다.

남규는 총 N-1번의 경기 동안, 경기 순서와 승패를 잘 정해서 시청률의 총합을 최대화한다면 어느 정도까지 시청률의 합이 커질 수 있는지가 궁금해졌다.

경기의 순서와 승패를 잘 정해, 시청률의 합의 최댓값을 구해 보고, 경기가 어떻게 진행되어야 하는지 정해 보자.

입력

첫째 줄에 참가하는 요리사의 수 N이 주어진다. (2 ≤ N ≤ 1000)

이어 N줄에 걸쳐, 각 요리사의 요리 실력 P_i와 인기도 C_i가 주어진다. (0 ≤ P_i, C_i ≤ 10⁹, P_i ≠ P_j if i ≠ j)

출력

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

둘째 줄부터 N번째 줄까지, 대결하는 두 요리사의 번호를 “패자 승자” 의 형식으로 대결한 순서대로 출력한다.

승자가 천국으로 떠나고, 패자는 계속 남아 대결을 진행하게 되는 것임에 주의한다.

만일 시청률의 합이 최대가 되는 대진표가 여러 가지 있다면 그 중 임의의 하나를 출력해도 정답으로 인정된다.

제한

힌트