Problem F
Línuhlýnun

Image from flickr.com

The residents of Lineland recently received the news that a university was going to be built in the country. This is exciting news, especially since linear algebra, linear optimization and linear functional analysis will all be taught among other exciting subjects.

The greenhouse effect has affected Lineland like other countries and this has caused linewarming. Authorities worry that this could worsen when the students of the new university drive to school, since that could increase the amount of carbon dioxide in the air. They have thus gotten you to choose the location of the school that will minimize pollution.

As the name suggests the citizens of Lineland live on a line. House numbers in the country are positive integers, but the distance between house number $a$ and $b$ is $|a-b|$ kilometers.

Given a list of the university’s students, where they live, and how much their car pollutes per kilometer, find at which house number it would be best to build the university to minimize the total carbon dioxide output each morning as students drive to school.

Note that several students can live at the same house. It is also acceptable to build the university where students already live, they will simply get the privilege of living at the university.

Input

The first line of the input contains a single integer $n$ ($1 \leq n \leq 2\cdot 10^5$), the number of students at the new university.

Then there are $n$ lines, one for each student, where line number $i$ contains two integers $x_i$ ($1 \leq x_i \leq 10^9$), the number of the house the $i$-th student lives in, and $c_i$ ($1 \leq c_i \leq 10^3$), the amount of carbon dioxide the $i$-th students’ car pollutes per kilometer.

Output

Print at what house number it would be best to build the university to minimize pollution from students driving to school every morning. If several house numbers are possible, print the smallest one.

Scoring

3
1 1
2 1
5 1

2

3
1 1
2 1
5 3

5

4
9 2
4 1
18 4
4 2

9