#CF2266F. MEX Replacement

MEX Replacement

题目描述

给你一个以压缩形式表示的非负整数多重集。即,对于多重集中的每个值 xix_i,你知道它的出现次数 yiy_i。

在一次操作中,你可以选择当前多重集中任意非空的元素集合,移除所有被选中的元素,并插入一个等于它们的 MEX⁡\operatorname{MEX}∗^{\text{∗}} 的元素。

你可以执行操作任意次数,包括零次。

求在任意时刻多重集中可能出现的最大整数。

∗^{\text{∗}}一个整数集合 c1,c2,…,ckc_1,c_2,\ldots,c_k 的最小排除值(MEX)是不在该集合中出现的最小非负整数 xx。

输入格式

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4)— 测试用例的数量。

每个测试用例的第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)— 初始多重集中不同整数的数量。

接下来 nn 行,每行包含两个整数 xix_i 和 yiy_i(0≤xi≤1090 \le x_i \le 10^9,1≤yi≤1091 \le y_i \le 10^9),表示整数 xix_i 在初始多重集中恰好出现 yiy_i 次。

整数 x1,x2,…,xnx_1,x_2,\ldots,x_n 两两不同。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例,输出一个整数 — 在任意时刻多重集中可能出现的最大整数。

样例

10
4
2 2
0 3
4 1
1 2
1
10 1
1
2 3
3
0 1
2 2
3 1
3
0 4
1 2
2 1
1
0 100
2
2 7
3 1
2
0 1
3 3
3
0 1
1 1
59 1
4
0 5
1 1
2 3
3 1
5
10
3
4
4
7
4
3
59
5

说明

在第一个测试用例中,初始多重集为 {0,0,0,1,1,2,2,4}\{0,0,0,1,1,2,2,4\}。

我们可以将 {0,1,2}\{0,1,2\} 替换为 33,得到 {0,0,1,2,3,4}\{0,0,1,2,3,4\}。然后,我们可以将 {0,1,2,3,4}\{0,1,2,3,4\} 替换为 55。

可以证明不会出现大于 55 的整数,因此答案为 55。

在第二个测试用例中,1010 已经出现在初始多重集中,且不会出现更大的整数。因此答案为 1010。

来源

导入自 Codeforces — Codeforces Round 1122 (Div. 3)。