说明

小$C$ 不喜欢上班。 他的老板又给小$C$安排了$n$项任务。 老板担心小$C$在公司里不干活儿， 于是给每一项任务安排了一个最迟动工时间$t_i$， 当超过时间 $t_i$时（ 不包括$t_i$这个时间点） ， 如果小 $C$ 仍未动工， 就会被扣薪。 小$C$ 可以选择在 $t_i$ 时刻之前或者恰好在$t_i$时刻办这项任务， 一旦选择开始办， 就必须连续不断、 且时长达到$l_i$才能完成这项任务。

在任意时刻下， 小 $C$ 最多只能做一项任务。 小 $C$ 很懒， 他想合理安排任务顺序， 使得开始办第一项任务的时间尽可能地迟， 并且不会被扣薪。

注意开始时间可能为负数。

输入格式

第一行一个正整数$n$， 表示任务个数；

接下来$n$ 行， 每行两个整数$t_i$ 和 $l_i$ ， 表示每项任务最迟动工时间以及完成任务所需的 工作时长

输出格式

仅一行一个数， 表示最迟的工作时间

样例

2
1 4
2 2

-1

【 样例 1 解释】

按照 2、 1 的任务顺序， 工作的时间区间为 [−1,1][1,5]。 显然开始工作的时间不能 迟于时刻 −1

5
2 5
3 3
7 4
8 2
10 1

-4

【 样例 2 解释】

按照 2、 1、 5、 4、 3 的任务顺序， 工作的时间区间为 [−4,−1][−1,4][4,5][5,7][7,11]

数据范围

• 对于 10% 的数据：$n = 2$
• 对于 30% 的数据： $n ≤ 10$
• 对于 60% 的数据：$n ≤ 5 × 10^3$
• 对于 100% 的数据：$n ≤ 2 × 10^5， 0 < l_i ,ti≤ 10^9$

来源

2021 年合肥市青少年信息学科普日活动(初中组)