Airplane Boarding Delay

Farmer John's cows have found an airline willing to sell them tickets. The airplane has \(N\) seats, represented as the points \(1, 2, \dots, N\) on the number line. There are \(N\) cows waiting in line to board. The front cow (cow \(N\)) is at position \(0\), the next (cow \(N-1\)) is at position \(-1\), and so on, with cow \(i\) starting at position \( - (N-i) \). Each cow \(i\) is assigned a unique seat \(S_i\) (a permutation of \(1,2,\dots,N\)).

The cows move in discrete time steps. At each second, every cow moves one unit to the right, provided she is not blocked by a cow directly in front of her. When cow \(i\) reaches her assigned seat \(S_i\), she stops and takes \(T_i\) seconds to store her baggage in the overhead bin before sitting down. During these \(T_i\) seconds the aisle is blocked; any cow immediately behind (and the entire line behind her) cannot move until cow \(i\) is seated.

Determine the minimum number of seconds required for all cows to be seated.

Note: The starting position of cow \(i\) is \( - (N-i) \) and, if there were no delays, the natural time for cow \(i\) to reach her seat would be \(S_i + (N-i)\) seconds. However, blocking due to baggage delays may force later cows to wait.

Input Constraints:

• \(1 \le N \le 200{,}000\)
• The sum of all \(T_i\) is less than \(10^9\).

inputFormat

The input begins with a single integer \(N\) on the first line, denoting the number of cows. Following this, there are \(N\) lines. The \(i\)th of these lines contains two integers \(S_i\) and \(T_i\), which are the assigned seat for cow \(i\) and the time in seconds required for her baggage, respectively.

Note that the cows are given in order from cow 1 (at position \( - (N-1) \)) to cow \(N\) (at position 0).

outputFormat

Output a single integer: the minimum number of seconds required for all cows to be seated.

sample

1
1 5

6