题目描述

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

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

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

输入格式

从文件 work.in 中读取数据。

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

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

输出格式

输出到文件 work.out 中。

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

样例

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,t_i≤10^9$。