Elevator

You have a very important job: you are responsible for an elevator in a new skyscraper.

There are $n$ people who will come to the underground parking garage on floor $0$ and wait for an elevator to take them to some upper floor. Formally, the $i$-th person comes to the elevator at moment $t_i$ and wants to reach floor $a_i$. The elevator has infinite capacity, so there is no limit on the number of people using the elevator at any moment. All $t_i$ are distinct. Passengers always enter the elevator while it is at floor $0$.

The elevator uses the following algorithm: it stays open on floor $0$ until you send it to deliver passengers, then it moves to the highest floor it needs to reach (the maximum $a_i$ among all passengers currently in the elevator), dropping passengers off along the way, and returns to the parking garage. The elevator spends $1$ unit of time to move to the next floor (or to the previous floor). The time spent opening and closing the elevator doors and letting passengers enter and leave is negligible. At moment $0$, the elevator is at floor $0$.

You want to minimize the moment of time when the elevator will return to floor $0$ after delivering everyone.

The input contains one or more test cases.

The first line of each test case contains one integer $n$: the number of passengers ($1 \le n \le 2 \cdot 10^5$).

Each of the following $n$ lines contains two space-separated integers $t_i$ and $a_i$: the moment of time when the $i$-th passenger comes to the elevator, and the destination floor of the $i$-th passenger ($1 \le t_i, a_i \le 10^9$).

All $t_i$ in one test case are distinct, and passengers appear in the input in ascending order of $t_i$.

The sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$. The test cases just follow one another without any special separators.

For each test case, print one integer: the minimum possible moment of time when the elevator will return after delivering all passengers.