问题描述

高桥君记住了 $N$ 个魔法。这些魔法从 $1$ 到 $N$ 编号。

初始时，温度为 $0$ 度。当高桥君施展第 $i$ 个魔法时，温度会上升 $a_i$ 度，然后下降 $b_i$ 度。

高桥君会唱出所有魔法，每个魔法恰好一次。我们定义这段时间内的最高温度为 $X$ 度。高桥君想要通过调整施展魔法的顺序，尽可能地减小 $X$。请计算 $X$ 的最小值。

约束条件

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

输入

输入通过标准输入获得，格式如下。

$N$ $a_1$ $b_1$ $:$ $a_N$ $b_N$

输出

输出 $X$ 的最小值。

示例输入1

1
10 20

示例输出1

10

当唱出唯一的一个魔法时，温度变化为 $0$ → $10$ → $\-10$ 度。

示例输入2

2
30 20
10 20

示例输出2

20

按照第 $2$ 个魔法，然后是第 $1$ 个魔法的顺序施展魔法时，温度变化为 $0$ → $10$ → $\-10$ → $20$ → $0$ 度。

示例输入3

5
5 10
10 5
10 15
15 10
20 20

示例输出3

10

例如，按照 $1$，$3$，$5$，$2$，$4$ 的顺序施展魔法即可。