Airplane Boarding

Farmer John's cows decided to take a vacation, and they managed to find an airline willing to sell them tickets. When they arrive at the airport and start boarding their plane, they run into an interesting problem.

The plane has $N$ seats, which we model as the points $x = 1$ through $x = N$ on the number line. All $N$ cows are standing in line waiting to get to their seats. Cow $N$ is at position $x = 0$, cow $N-1$ is at position $x = -1$, and the rest line up one step further back in the same way. Cow $i$ has been assigned seat $S_i$, where $S_1, \dots, S_N$ is a permutation of $1$ through $N$.

Every second, each cow takes one step to the right if she can. When cow $i$ reaches her seat $S_i$, she stops to put her baggage in the overhead bin, which takes $T_i$ seconds, and then sits down. During those $T_i$ seconds the cow right behind her cannot move forward, and if a line of cows has formed behind her, that line is stuck as well.

How long does it take for all the cows to sit down?

$N$ is between 1 and 200,000, and the sum of all $T_i$ is less than 1,000,000,000.

The first line contains the integer $N$. The $i$-th of the next $N$ lines contains two space-separated integers $S_i$ and $T_i$.

Print on a single line the amount of time it takes to seat all the cows.

Suppose there are three cows, cow 1 heads for seat 2, cow 2 heads for seat 3, and cow 3 heads for seat 1, with baggage times of 5, 10, and 5 seconds. At the start cow 3 stands at $x = 0$, cow 2 at $x = -1$, and cow 1 at $x = -2$.

After one second all three move one step to the right and cow 3 reaches her seat. She needs 5 seconds to stow her baggage and sit down, and the two cows behind her stay put that whole time. Once she sits down she is effectively gone from the aisle.

Over the next 3 seconds cow 1 and cow 2 each reach their own seat. Cow 1 needs 5 seconds to sit down and cow 2 needs 10, and they stow their baggage at the same time, so 10 more seconds pass. The whole thing takes $1 + 5 + 3 + 10 = 19$ seconds.