题目描述

FJ's cows have decided to take a vacation, and have miraculously managed to find an airline willing to sell them tickets. When they arrive at the airport and start boarding their plane, they face an interesting problem, however.

The airplane has $N$ seats, which we model as the points $x=1$ through $x=N$ on the number line. All N cows $(1 \le N \le 200,000)$ 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 so on. Cow i has been assigned to Seat $S_i$, where $S_1$,...,$S_N$ is a permutation of $1$,...,$N$.

At each time step, each cow takes a step to the right if she can. When cow $i$ reaches her seat $S_i$, she will stop to put her baggage in the overhead bin, which takes $T_i$ seconds, and then sit down. For those $T_i$ steps, the cow behind her (if there is one) is blocked from moving forward. If there is a line of cows behind her, the line is effectively blocked as well.

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

The sum of $T_i$ for all cows will be less than $1,000,000,000$.

输入格式

• Line $1$: A single integer, $N$.

• Lines $2$..$N+1$: Two space-separated integers, $S_i$ and $T_i$.

输出格式

• Line $1$: A single line indicating the amount of time it takes to seat all cows.

3 
2 5 
3 10 
1 5 

19 

提示

Initially, the cows are situated like this:

cows -> $123$

$123$ <- seats

with cow $1$ trying to get to seat $2$, cow $2$ trying to get to seat $3$, and cow $3$ trying to get to seat $1$.

After one step, they will all move $1$ to the right and cow $3$ will reach her seat:

123 123 Cow $3$ takes $5$ seconds to sit down, at which point she effectively disappears.

12 123 It takes $3$ more seconds for cows $1$ and $2$ to reach their desired seats:

12 123 It takes $5$ seconds for cow $1$ to sit down and $10$ seconds for cow $2$ to sit down, so that's $10$ seconds total.

In total this took $1 + 5 + 3 + 10 = 19$ seconds.