Post Office

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

You want to build one post office for these villages. Its location should minimize the sum of distances from the post office to every person. Write a program that outputs the location.

Be careful that the sum is over all people, not just over villages: a village with A[i] residents contributes A[i] times its distance.

The first line contains N (1 <= N <= 100,000). Each of the next N lines contains the position X[i] and population A[i] of one village.

All input values are integers, |X[i]| <= 1,000,000,000, and 1 <= A[i] <= 1,000,000,000.

Print the position of the post office that minimizes the sum of distances to all people. If there are multiple possible positions, print the smallest one.