题目描述

你正在参加国际合并专业大赛(International Combination Professional Contest, ICPC)。给定 $n$ 个集合的 MEX 值 $x$ 和集合大小 $\ell$，求将 $n$ 个集合合并后最大的 MEX 可能值。

定义一个集合 $S$ 的 MEX(Minimal Excludant) 表示一个非负整数集合中，“最小的”、“没有出现过”的非负整数。数学上定义为

$$\operatorname{mex}(S)=\min\left\{ x\in\mathbb{N} \mid x\notin S\right\}$$

例如：$\operatorname{mex}(\left\{ 0,1,2,3,4,7,8 \right\})=5$。

输入描述

第一行为一个整数 $n$ 表示集合的数量，满足 $1\leqslant n\leqslant 2\times 10^5$。

接下来 $n$ 行，第 $i$ 行两个空格隔开的整数 $x_i,\ell_i$，分别表示第 $i$ 个集合的 MEX 值和集合大小，满足 $0\leqslant x_i\leqslant \ell_i\leqslant 1\times 10^9$。

输出描述

输出一个整数表示集合合并后的最大可能值。

样例

3
16 18
12 16
0 9

31

4
114 514
5 5
6 6
7 7

114