Problem Description

Laifang Road is a road with a length of \( L \) meters. The coordinates on the road range from \( 0 \) to \( L \). There are \( N \) houses on the road, with the \( i \)-th house built at coordinate \( x_i \) and inhabited by \( r_i \) people.

The Songjiang 1843 Road bus service plans to establish a bus stop on this road. The municipal government aims to provide convenience to the maximum number of people, thus hoping to minimize the total distance from each resident's home to the bus stop.

Where should the bus stop be built?

Input Format

The first line contains two integers \( L \) and \( N \).

The next \( N \) lines each contain two integers \( x_i \) and \( r_i \).

Output Format

Output a single integer, the minimum total distance from each home to the bus stop.

Sample Input and Output

Sample Input #1

100 3
20 3
50 2
70 1

Sample Output #1

110

Sample Input #2

100 2
0 1
100 10

Sample Output #2

100

Sample Input #3

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

Sample Output #3

5473201404068

Notes

Sample Explanation 1

When the bus stop is built at coordinate \( 40 \), the total distance for all residents to the bus stop is \( |20-40| \times 3 + |50-40| \times 2 + |70-40| \times 1 = 110 \).

Data Range and Constraints

For \( 10\% \) of the data, \( 1 \le N \le 50 \), \( R_i = 1 \).

For \( 30\% \) of the data, \( 1 \le N \le 100 \), \( R_i \le 10 \), \( 1 \le L \le 1000 \).

For \( 70\% \) of the data, \( 1 \le N \le 1000 \), \( R_i \le 100 \), \( 1 \le L \le 10^6 \).

For all data, \( 1 \le L \le 10^{10} \), \( 1 \le N \le 10^5 \), \( 0 \le x_i \le L \), \( 1 \le r_i \le 1000 \).

见题面 Input 部分

见题面 Output 部分