该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P5120 [USACO18DEC] Convention II S

题目描述

虽然在接机上耽误了挺长时间，Farmer John 为吃草爱好牛们举行的大会至今为止都非常顺利。大会吸引了世界各地的奶牛。

然而大会的重头戏看起来却给 Farmer John 带来了一些新的安排上的困扰。他的农场上的一块非常小的牧草地出产一种据某些识货的奶牛说是世界上最美味的品种的草。因此，所有参会的 $N$ 头奶牛（$1\le N\le 10^5$）都想要品尝一下这种草。由于这块牧草地小到仅能容纳一头奶牛，这很有可能会导致排起长龙。

Farmer John 知道每头奶牛 $i$ 计划到达这块特殊的牧草地的时间 $a_i$，以及当轮到她时，她计划品尝这种草花费的时间 $t_i$。当奶牛 $i$ 开始吃草时，她会在离开前花费全部 $t_i$ 的时间，此时其他到达的奶牛需要排队等候。如果这块牧草地空出来的时候多头奶牛同时在等候，那么资历最深的奶牛将会是下一头品尝鲜草的奶牛。在这里，恰好在另一头奶牛吃完草离开时到达的奶牛被认为是“在等待的”。类似地，如果当没有奶牛在吃草的时候有多头奶牛同时到达，那么资历最深的奶牛是下一头吃草的奶牛。

请帮助 FJ 计算所有奶牛中在队伍里等待的时间（$a_i$ 到这头奶牛开始吃草之间的时间）的最大值。

输入格式

输入的第一行包含 $N$。以下 $N$ 行按资历顺序给出了 $N$ 头奶牛的信息（资历最深的奶牛排在最前面）。每行包含一头奶牛的 $a_i$ 和 $t_i$。所有的 $t_i$ 为不超过 $10^4$ 的正整数，所有 $a_i$ 为不超过 $10^9$ 的正整数。

输出格式

输出所有奶牛中的最长等待时间。

输入输出样例 #1

输入 #1

5
25 3
105 30
20 50
10 17
100 10

输出 #1

10

说明/提示

在这个例子中，我们有 $5$ 头奶牛（按输入中的顺序编号为 $1\dots 5$）。奶牛 $4$ 最先到达（时间 $10$），在她吃完之前（时间 $27$）奶牛 $1$ 和奶牛 $3$ 都到达了。由于奶牛 $1$ 拥有较深的资历，所以她先吃，从她到达开始共计等待了 $2$ 个单位时间。她在时间 $30$ 结束吃草，随后奶牛 $3$ 开始吃草，从她到达开始共计等待了 $10$ 单位时间。在一段没有奶牛吃草的时间过后，奶牛 $5$ 到达，在她正在吃草的时间里奶牛 $2$ 也到达了，在 $5$ 个单位时间之后能够吃到草。相比到达时间等待最久的奶牛是奶牛 $3$。