[USACO14FEB] Airplane Boarding G

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 <= 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. 想象一下飞机有N个座位，N个座位相当于数轴上的1至N共N个整点，第1个座位在整点1处，第2个座位在整点2处，……第N个座位在整点N处。 有N个奶牛排好队，要登陆坐飞机，第N头奶牛在数轴的整点0处，第N−1头奶牛在数轴的整点−1处，……第1头奶牛在数轴的整点−N+1处。第i头奶牛的座位号是Si。注意：每头奶牛都有唯一的一个座位，不会出现多头奶牛有相同的座位号。 在每一秒钟，奶牛会向右移动一步到达下一个整点，前提是没有奶牛挡住它。 当第i头奶牛到达它的座位Si时，它需要花费Ti秒去把行李放到头顶的行李架上，然后坐到自己的位置上，在此过程中，由于飞机通道很窄，所以在第i头奶牛坐到自己座位之前，在它左边的所有奶牛都不能动，要等奶牛i放好行李坐好后才能动。 现在的问题是，至少要多少秒之后，所有的奶牛都能做到自己的座位上？

\* 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.