#CF2266F. MEX Replacement
MEX Replacement
Problem Description
You are given a multiset of non-negative integers in compressed form. That is, for each value $x_i$ in the multiset, you know the number of its occurrences $y_i$.
In one operation, you may choose any non-empty collection of elements currently in the multiset, remove all chosen elements, and insert one element equal to their $\operatorname{MEX}$$^{\text{∗}}$.
You may perform the operation any number of times, possibly zero.
Find the maximum integer that can appear in the multiset at any moment.
$^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $c_1,c_2,\ldots,c_k$ is the smallest non-negative integer $x$ that does not occur in the collection.
Input Format
The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of distinct integers in the initial multiset.
Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i \le 10^9$, $1 \le y_i \le 10^9$), indicating that the integer $x_i$ occurs exactly $y_i$ times in the initial multiset.
The integers $x_1,x_2,\ldots,x_n$ are pairwise distinct.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
Output Format
For each test case, output one integer — the maximum integer that can appear in the multiset at any moment.
Examples
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
Note
In the first test case, the initial multiset is $\{0,0,0,1,1,2,2,4\}$.
We can replace $\{0,1,2\}$ with $3$, obtaining $\{0,0,1,2,3,4\}$. Then, we can replace $\{0,1,2,3,4\}$ with $5$.
It can be shown that no integer greater than $5$ can appear, so the answer is $5$.
In the second test case, $10$ already appears in the initial multiset, and no greater integer can appear. Thus, the answer is $10$.
Source
Imported from Codeforces — Codeforces Round 1122 (Div. 3).