Post Office

There are N villages on a number line. The i-th village is at coordinate X[i] and has A[i] residents.

You need to build one post office for these villages. Choose a position that minimizes the sum of the distances from the post office to every resident. Determine such a position.

The distance sum is computed over individual residents, not over villages.

The first line contains the number of villages N (1 ≤ N ≤ 100,000).

Each of the next N lines contains the coordinate X[i] of a village and its number of residents A[i]. All values are integers, with |X[i]| ≤ 1,000,000,000 and 0 ≤ A[i] ≤ 1,000,000,000.

The sum of all A[i] is greater than 0.

Print the position where the post office should be built. If there are multiple optimal positions, print the smallest one.