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

The airplane has N seats, which we model as the points x=1 through x=N on the number line. All N cows (1 <= N <= 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.

A single line indicating the amount of time it takes to seat all cows.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > February > Gold