题目描述

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$。