P3819 Songjiang 1843 Road

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?

The first line contains $L$, $N$. The next $N$ lines each contain two integers $x_i$ and $r_i$.

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

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