405014: GYM101741 D Elevator

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

There are n persons who will come to the underground parking located on floor 0 and wait for an elevator to bring them to some upper floor. Formally, i-th person comes to the elevator at moment t_i and wants to reach floor a_i. The elevator has infinite capacity; that is, there is no limit on the number of people using the elevator at any moment. All numbers t_i are distinct. Passengers always enter the elevator as long as 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 (the maximum a_i among all passengers who are currently in the elevator), distributing the passengers in the process, and returns to the parking. The elevator spends 1 unit of time to move to the next floor (or to the previous floor). The time spent for opening and closing the doors of the elevator, as well as for the passengers entering and leaving the elevator, 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 ≤ n ≤ 2·10⁵).

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

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

The sum of the values of n over all test cases does not exceed 2·10⁵. 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.

3
1 9
2 6
15 6
3
1 9
2 6
15 8

31
33