[USACO FEB14]登机

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file boarding.in Output file boarding.out

【题目描述】


FJ的牛已经决定去度假,并奇迹般地找到一个航空公司愿意出售他们的票。然而,当他们到达机场开始登机,面临的是一个有趣的问题 。

飞机有N个座位,我们叫位置x = 1到x = N,在一个数轴上。所有的奶牛 (1 <= N <= 200,000)正在排队在等待进入他们的座位。刚开始,奶牛N是在位置x = 0,奶牛N-1是在位置x = -1,等等。牛i被分配到牛座s_i,这里s_1,……,s_n是排列1,……,N.

在每一个时间步,每头奶牛需要走一步找到正确的座位如果她能。当奶牛i一到她的座位s_i,她将停下来,把她的行李放在上面的行李架上,用时t_i秒,然后坐下来。对于那些t_i秒时间,在她后面(如果有)的牛会被阻止向前。如果有一队牛在她身后,都将被阻止向前。

所有的牛坐好需要多久?

所有奶牛的t_i将少于1000000000。


【输入格式】


第1行为N;

接下来有N行(2--N+1),两个整数s_i和t_i;



【输出格式】


输出只有一行,即需要的时间。



【样例输入】

3
2 5
3 10
1 5

【样例输出】

19

【提示】


输入输出解释:
最初,牛是位于这样:
牛 -> 123 123<- 座椅

  -2 -1 0 1 2 3
1 2 3      
座椅       1 2 3

牛1试图去坐2,2只想坐3,和牛3要座1。

一步后,他们都会向前走1步,牛3将达到她的座位1.
  -2 -1 0 1 2 3
  1 2 3    
座椅       1 2 3
牛3用时5秒放行李,然后坐到座位上.
  -2 -1 0 1 2 3
  1 2      
座椅       1 2 3

3秒后奶牛1和奶牛2达到自己想要的座位:

 
 
 
  -2 -1 0 1 2 3
        1 2
座椅       1 2 3

需要5秒的奶牛1坐下来,10秒奶牛2坐下来,总共需要10秒

这一共花了1 + 5 + 3 + 10 = 19秒。

 


【来源】

在此键入。