Type: Default 2000ms 512MiB

MEX 合并

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

定义一个集合 SS 的 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$。

输入描述

第一行为一个整数 nn 表示集合的数量,满足 1⩽n⩽2×1051\leqslant n\leqslant 2\times 10^5。

接下来 nn 行,第 ii 行两个空格隔开的整数 xi,ℓix_i,\ell_i,分别表示第 ii 个集合的 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