로봇들의 모험

$1$번부터 $N$번까지 번호가 부여된 $N$대의 로봇이 출발지에 있다. 이 중 $i$번 로봇은 최대 $k_i$대의 다른 로봇을 실을 수 있고 거리 $d_i$를 이동할 수 있다.

처음에 한 로봇이 다른 로봇 $0$대 이상을 싣고 출발지에서 출발하여 자신이 이동할 수 있는 만큼 이동한 후, 싣고 온 모든 로봇을 내려 놓는다. 그 장소에서, 내려 놓은 로봇 중 한 대가 그 장소까지 실려 온 나머지 로봇들 전부 혹은 일부를 싣고 다시 출발하여 동일한 과정을 반복한다.

더 이상 이동할 수 있는 로봇이 없을 때까지 위 과정을 반복하여 마지막에 이동한 로봇이 도달할 수 있는, 최대 거리를 계산하는 프로그램을 작성하라. 최대 거리는 출발지로부터의 거리를 의미한다.

입력 형식

첫 줄에 로봇의 대 수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 200\,000$)

그다음 $N$개의 줄 중 $i$번째 줄에는 $i$번 로봇에 대한 정보를 나타내는 두 정수 $k_i$와 $d_i$가 공백으로 구분되어 주어진다. ($0 \le k_i \le N;$ $1 \le d_i \le 10\,000$)

출력 형식

첫 줄에 최대 거리를 출력한다.

예제 1

4
3 3
0 2
4 10
4 5

20

예제 2

5
0 7
2 4
0 3
1 1
2 2

13

예제 설명

• 예제 1에서는, 로봇들이 실을 수 있는 대 수가 충분히 많으므로 여러 가지 방법으로 총 거리 $20$을 이동할 수 있다. 단, 제일 마지막에 이동하는 로봇은 $2$번 로봇이어야 한다.
• 예제 2에서는, $5$번 로봇이 $1$번과 $2$번 로봇을 싣고 출발하여 거리 $2$를 이동한다. 내려 놓은 $1$번과 $2$번 로봇들 중 $2$번 로봇이 $1$번 로봇을 싣고 거리 $4$를 이동한다. 마지막으로 $1$번 로봇이 다른 로봇을 싣지 않고 거리 $7$을 이동한다. 이 경우, 총 이동 거리는 $2 + 4 + 7 = 13$이다.

채점 방식

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

해설