题目描述

高桥君会 $N$ 个魔法。将这些魔法分别编号为 $1$ 到 $N$ 。

开始时，气温为 $0$ 度。高桥君咏唱第 $i$ 个魔法后，气温会先上升 $a_i$ 度再下降 $b_i$ 度。

高桥君会将所有魔法都咏唱一遍。这期间气温的最大值为 $X$ 度。高桥君可以自己决定咏唱魔法的顺序，来使 $X$ 的值尽量小。

求最小的 $X$ 值。

数据范围

• $1 \le N \le 10^5$
• $a_i,b_i$ 都是整数。
• $1 \le a_i,b_i \le 10^9$

输入输出格式

输入格式：

输入按以下形式：

输出格式：

输出 $X$ 的最小值。

输入输出样例

输入样例1

1
10 20

输出样例1

10

样例解释1

咏唱唯一一个魔法。气温的变化如下：$0 → 10 → -10$ 。

输入样例2

2
30 20
10 20

输出样例2

20

样例解释2

先咏唱第 $2$ 个魔法，再咏唱第 $1$ 个魔法，气温变化如下： $0 →10 → -10 → 20 → 0$ 。

输入样例3

5
5 10
10 5
10 15
15 10
20 20

输出样例3

10

样例解释3

举例来说，可以按 $1,3,5,2,4$ 的顺序咏唱魔法。