1591. [USACO Feb14]登机

【题目描述】

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<- 座椅

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

一步后，他们都会向前走1步，牛3将达到她的座位1.

牛3用时5秒放行李，然后坐到座位上.

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

 

 

 

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

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

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

【来源】

在此键入。