Equilibrium Knot

There are n heavy objects, each attached to a sufficiently long elastic rope. Every rope passes from the top of a table through a small circular hole, and all the ropes are tied together at a common knot x below the table. Note that the holes on the table are very small compared to the knot, so even if one object is very heavy, the knot can never fall through a hole—it can only get caught at one of them.

Assuming that the ropes are perfectly elastic (i.e. no energy loss) and friction is negligible, the system will eventually reach an equilibrium state. In that state, each heavy object exerts a horizontal pull equal to its weight. The equilibrium position is achieved when the total weight of objects attached to ropes whose holes are to the left of the knot is no more than half of the total weight, and similarly for those on the right. In other words, if each object is associated with a hole position h_i and weight w_i, then after sorting the pairs in increasing order of h, letting the total weight be

[ W = \sum_{i=1}^{n}w_i, ]

the equilibrium knot position is the smallest h_j such that

[ \sum_{i=1}^{j}w_i \geq \frac{W}{2}. ]

Output that h_j as the equilibrium horizontal position of the knot.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of heavy objects (and ropes).

Each of the next n lines contains two space-separated integers h and w (1 ≤ h, w ≤ 10⁹), where h is the horizontal position of the hole on the table for that rope, and w is the weight of the heavy object attached to that rope.

You may assume that multiple ropes can have the same hole position.

outputFormat

Output a single integer — the horizontal position of the knot at equilibrium.

sample

3
1 3
2 3
3 3

2