[Usaco2014 Feb]Airplane Boarding

题目描述

  想象一下火车有N个座位，N个座位相当于数轴上的１至Ｎ共Ｎ个整点，第1个座位在整点1处，第2个座位在整点2处，。。。第N个座位在整点N处。 有N个奶牛排好队，要登陆坐火车，第N头奶牛在数轴的整点0处，第N-1头奶牛在数轴的整点-1处，。。。。第1头奶牛在数轴的整点-N+1处。第i头奶牛的座位号是Si。注意：每头奶牛都有唯一的一个座位，不会出现多头奶牛有相同的座位号。 

在每一秒钟，奶牛会向右移动一步到达下一个整点，前提是没有奶牛挡住它。 当第i头奶牛到达它的座位Si时，它需要花费Ti秒去把行李放到头顶的行李架上，然后坐到自己的位置上，在次过程中，由于火车通道很窄，所以在第i头奶牛坐到自己座位之前，在它左边的所有奶牛都不能动，要等奶牛i放好行李坐好后才能动。      

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

---

输入格式

 第一行，一个整数N。1 <= N <= 200000。 

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

---

输出格式

一个整数。 

---

样例输入

3
2 5
3 10
1 5

---

样例输出

19
 

---

提示

 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. 

---

题目来源

Gold