Convention II

题目描述

尽管机场接机出现了长时间延误，Farmer John 为想吃草的奶牛们举办的大会到目前为止进展顺利，吸引了来自世界各地的奶牛。

然而，大会的主活动看起来可能会给 Farmer John 带来进一步的日程安排烦恼。他农场里有一小块牧场，生长着一种稀有草，据有品味的奶牛称其是世界上最美味的草。因此，参会的全部 $N$ 头奶牛（$1 \leq N \leq 10^5$）都想品尝这种草。由于牧场非常小，一次只能容纳一头奶牛，这很可能导致排起长队。

Farmer John 知道每头奶牛 $i$ 计划到达这块特殊牧场的时间 $a_i$，以及轮到她时计划花费在品尝这种草上的时间 $t_i$。一旦奶牛 $i$ 开始吃草，她会完整地吃满 $t_i$ 的时间后才离开，在此期间其他到达的奶牛都需要等待。如果在牧场再次空出来时有多头奶牛正在等待，那么资历（seniority）最高的奶牛将下一位被允许品尝草。为此，若一头奶牛恰好在另一头奶牛结束吃草的时刻到达，则也被视为“正在等待”。同样地，如果在没有奶牛正在吃草时，有若干头奶牛恰好同时到达，那么资历最高的那头将下一位开始吃。

请帮助 FJ 计算任意一头奶牛在队伍中可能需要等待的最大时间（从时间 $a_i$ 到该奶牛开始吃草的时间之间）。

输入格式

第一行输入为 $N$。接下来的 $N$ 行按资历从高到低的顺序给出这 $N$ 头奶牛的详细信息（资历最高的奶牛在最前）。 每行包含一头奶牛的 $a_i$ 和 $t_i$。其中 $t_i$ 为正整数且不超过 $10^4$，$a_i$ 为正整数且不超过 $10^9$。

输出格式

请输出所有奶牛中可能出现的最长等待时间。

5
25 3
105 30
20 50
10 17
100 10

10

提示

在这个例子中，有 5 头奶牛（按输入顺序编号为 1..5）。奶牛 4 最先到达（时间 10），在她吃完之前（时间 27），奶牛 1 和 3 都到达了。由于奶牛 1 资历更高，她下一位开始吃，相比到达时间多等待了 2 个时间单位。她在时间 30 吃完，然后奶牛 3 开始吃，相比到达时间多等待了 10 个时间单位。在一段没有奶牛吃草的空档之后，奶牛 5 到达，且在她吃草期间奶牛 2 到达，之后延后了 5 个时间单位才开始吃。相对于到达时间被延误最多的是奶牛 3。 题目来源：Brian Dean

标签: USACO|2018|Silver

来源

USACO|2018|Silver