#2666. [cqoi2012]组装

题目描述

数轴上有 m 个生产车间可以生产零件。一共有 n 种零件，编号为1~ n 。第 i 个车间的坐标为 x i，生产第 _p i_种零件（1<= p i<= n ）。你需要在数轴上的某个位置修建一个组装车间，把这些零件组装起来。为了节约运输成本，你需要最小化cost(1)+cost(2)+…+cost( n )，其中cost( x )表示生产第 x 种零件的车间中，到组装车间距离的平方的最小值。

输入格式

输入第一行为两个整数 n , m ，即零件的种类数和生产车间的个数。以下 m 行每行两个整数 _x i_和 p i（1<= p i<= n ）。输入按照生产车间从左到右的顺序排列（即 x i<= x i+1。注意车间位置可以重复）。输入保证每种零件都有车间生产。

输出格式

输出仅一行，即组装车间的最优位置（可以和某个生产车间重合），四舍五入保留四位小数。输入保证最优位置惟一。

样例

样例输入

3 5  

-1 3  

0 1  

2 3  

4 2  

5 2  

样例输出

2.0000

数据范围与提示

编号

|

1-4

|

5-10

---|---|---

n

|

<=15

|

<=10000

m

|

<=25

|

<=100000

x i

|

<=100

|

<=100,000