비행기 탑승

휴가를 떠나기로 한 젖소들이 표를 파는 항공사를 겨우 찾아냈다. 그런데 공항에 도착해 비행기에 오르려는 순간 재미있는 문제를 만났다.

비행기의 좌석은 $N$개이고, 수직선 위의 $x = 1$부터 $x = N$까지의 점으로 나타낸다. 젖소 $N$마리가 자기 좌석으로 가려고 한 줄로 서 있다. $N$번 젖소는 $x = 0$, $N-1$번 젖소는 $x = -1$에 서 있고, 나머지도 같은 식으로 한 칸씩 뒤에 선다. $i$번 젖소가 배정받은 좌석은 $S_i$이고, $S_1, \dots, S_N$은 $1$부터 $N$까지의 순열이다.

매초 각 젖소는 오른쪽으로 한 칸 갈 수 있으면 간다. $i$번 젖소는 자기 좌석 $S_i$에 도착하면 짐을 머리 위 짐칸에 넣느라 $T_i$초 동안 그 자리에 서 있다가 앉는다. 그 $T_i$초 동안 바로 뒤 젖소는 앞으로 나아가지 못하고, 뒤로 줄이 이어져 있으면 그 줄도 함께 멈춘다.

모든 젖소가 자리에 앉기까지 몇 초가 걸리는지 구하시오.

$N$은 1 이상 200,000 이하이고, 모든 $T_i$의 합은 1,000,000,000보다 작다.

첫째 줄에 정수 $N$이 주어진다. 다음 $N$개 줄 중 $i$번째 줄에는 정수 $S_i$와 $T_i$가 공백으로 구분되어 주어진다.

모든 젖소가 자리에 앉기까지 걸리는 시간을 한 줄에 출력한다.

젖소가 세 마리이고 1번 젖소는 2번 좌석, 2번 젖소는 3번 좌석, 3번 젖소는 1번 좌석으로 간다고 하자. 짐을 넣는 시간은 차례로 5초, 10초, 5초다. 처음에 3번 젖소는 $x = 0$, 2번 젖소는 $x = -1$, 1번 젖소는 $x = -2$에 서 있다.

1초가 지나면 세 마리 모두 오른쪽으로 한 칸 움직이고, 3번 젖소가 1번 좌석에 도착한다. 3번 젖소가 짐을 넣고 앉는 데 5초가 걸리며, 그동안 뒤의 두 마리는 제자리에 멈춰 있다. 3번 젖소가 앉고 나면 통로에서 사라진 것과 같다.

이어지는 3초 동안 1번 젖소와 2번 젖소가 각자 자기 좌석에 도착한다. 1번 젖소는 앉는 데 5초, 2번 젖소는 10초가 걸리고 둘이 같이 짐을 넣으므로 10초가 더 필요하다. 그래서 전체 시간은 $1 + 5 + 3 + 10 = 19$초다.