Description

Laifang Road is a road of length $L$ meters, with coordinates ranging from $0$ to $L$. There are $N$ houses on the road. The $i$-th house is located at coordinate $x_i$ and has $r_i$ residents.

The Songjiang 1843 Road bus line will build a bus stop on this road. The city government wants to serve as many people as possible, so it hopes to minimize the sum of distances from every resident’s home to the stop.

Where should the bus stop be built?

Input Format

The first line contains $L$, $N$.

The next $N$ lines each contain two integers $x_i$ and $r_i$.

Output Format

Output one integer: the minimal sum of distances from all residents’ homes to the bus stop.

100 3
20 3
50 2
70 1

110

100 2
0 1
100 10

100

10000000000 5
3282894320 391
4394338332 929
6932893249 181
7823822843 440
9322388365 623

5473201404068

Hint

Sample Explanation 1

When the stop is built at coordinate $40$, the sum of distances is $|20-40| \times 3+|50-40| \times 2+|70-40| \times 1=110$.

Constraints

• For $10\%$ of the testdata, $1 \le N \le 50$, $r_i=1$.
• For $30\%$ of the testdata, $1 \le N \le 100$, $r_i \le 10$, $1 \le L \le 1000$.
• For $70\%$ of the testdata, $1 \le N \le 1000$, $r_i \le 100$, $1 \le L \le 10^6$.
• For all testdata, $1 \le L \le 10^{10}$, $1 \le N \le 10^5$, $0 \le x_i \le L$, $1 \le r_i \le 1000$.

Translated by ChatGPT 5