Post Office

Interview

Time limit2sMemory limit128 MB

Summary

Given villages with positions and populations on a line, find the point minimizing total weighted distance, choosing the smallest position on ties.

Level: Medium4 of 10
Topics: Sorting, Prefix sum, Greedy
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples1

Example 1
Input
```
3
1 3
2 5
3 3
```
Expected output
```
2
```