松江1843路

题目描述

涞坊路是一条长L米的道路,道路上的坐标范围从0到L,路上有N座房子,第i座房子建在坐标为x[i]的地方,其中住了r[i]人。 松江1843路公交车要在这条路上建一个公交站,市政府希望让最多的人得到方便,因此希望所有的每一个的居民,从家到车站的距离的**总和**最短。 公交站应该建在哪里呢?

输入输出格式

输入格式


第一行输入L、N。 接下来N行,每行两个整数x[i]和r[i]。

输出格式


一个整数,最小的每个人从家到车站的距离的总和。

输入输出样例

输入样例 #1

100 3
20 3
50 2
70 1

输出样例 #1

110

输入样例 #2

100 2
0 1
100 10

输出样例 #2

100

输入样例 #3

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

输出样例 #3

5473201404068

说明

样例解释1 当建在坐标40的时候,所有人距离车站的距离总和为 |20−40|×3+|50−40|×2+|70−40|×1=110。 数据范围和约定 对于10%的数据,1≤N≤50,R[i]=1。 对于30%的数据,1≤N≤100,R[i]≤10,1≤L≤1000。 对于70%的数据,1≤N≤1000,R[i]≤100,1≤L≤10^6。 对于全部数据,1≤L≤10^10,1≤N≤10^5,0≤x[i]≤L,1≤r[i]≤1000