Optimal Bus Station Location

Consider a road of length $L$ meters with coordinates ranging from $0$ to $L$. There are $N$ houses along the road, where the $i$-th house is located at coordinate $x_i$ and has $r_i$ residents. A bus station for the 松江 1843 route is to be built somewhere on this road. The city government wants to minimize the total distance all residents must travel from their homes to the bus station, that is, minimize the sum

$$\sum_{i=1}^{N} r_i\cdot |x_i - s|,$$

where $s$ is the location of the bus station. It can be shown that the optimal solution is given by a weighted median of the positions. If there are multiple optimal positions, output the smallest one.

inputFormat

The first line contains two integers $L$ and $N$ ($1 \le L \le 10^9$, $1 \le N \le 10^5$), representing the length of the road and the number of houses, respectively.

Each of the following $N$ lines contains two integers $x_i$ and $r_i$ ($0 \le x_i \le L$, $1 \le r_i \le 10^4$), representing the coordinate of the $i$-th house and the number of residents in that house.

outputFormat

Output a single integer — the coordinate at which the bus station should be built. If there are multiple optimal positions, output the smallest one.

sample

10 3
1 2
4 3
8 5

8