UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2666. [cqoi2012]组装

Statistics 下载数据

Description

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

Input

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

Output

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

 

Sample Input

3 5
-1 3
0 1
2 3
4 2
5 2

Sample Output

2.0000

Hint


























编号



1-4



5-10



n



<=15



<=10000



m



<=25



<=100000



xi



<=100



<=100,000



Source