UOJ Logo Universal Online Judge

UOJ

#3447. [Usaco2014 Feb]Airplane Boarding

统计

Description

  想象一下火车有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放好行李坐好后才能动。      

现在的问题是,至少要多少秒之后,所有的奶牛都能做到自己的座位上? 

Input

 第一行,一个整数N1 <= N <= 200000 

 接下来有N行,第i行有两个整数SiTi,表示第i头奶牛的参数。所有Ti之和不超过10^9    

Output

一个整数。 

Sample Input

3
2 5
3 10
1 5

Sample Output

19

Hint

 OUTPUT DETAILS: 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. 

Source

Gold