P0993

[cqoi2012]组装

数轴上有 mm 个生产车间，共生产 nn 种零件，零件编号为 1∼n1\sim n。第 ii 个生产车间的坐标为 xix_i，生产第 pip_i 种零件，其中 1≤pi≤n1\le p_i\le n。

你需要在数轴上的某个位置修建一个组装车间，将这些零件组装起来。定义 cost⁡(k)\operatorname{cost}(k) 为所有生产第 kk 种零件的车间到组装车间距离平方的最小值。为了节约运输成本，你需要最小化

∑k=1ncost⁡(k)。\sum_{k=1}^{n}\operatorname{cost}(k)。

输入格式

第一行包含两个整数 nn、mm，分别表示零件的种类数和生产车间的数量。

接下来 mm 行，每行包含两个整数 xix_i 和 pip_i，分别表示第 ii 个生产车间的坐标及其生产的零件种类，其中 1≤pi≤n1\le p_i\le n。

输入按照生产车间从左到右的顺序给出，即 xi≤xi+1x_i\le x_{i+1}。不同生产车间的坐标可以相同。

输入保证每种零件都至少有一个生产车间。

输出格式

输出一行，表示组装车间的最优位置。该位置可以与某个生产车间重合。

答案四舍五入保留 44 位小数。输入保证最优位置唯一。

样例输入

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

样例输出

2.0000

数据范围

  • 对于编号为 1∼41\sim 4 的测试点，n≤15n\le 15，m≤25m\le 25，∣xi∣≤100|x_i|\le 100；
  • 对于编号为 5∼105\sim 10 的测试点，n≤104n\le 10^4，m≤105m\le 10^5，∣xi∣≤105|x_i|\le 10^5；
  • 对于完整数据，xix_i 为整数，且 −105≤xi≤105-10^5\le x_i\le 10^5；
  • 对于所有数据，1≤pi≤n1\le p_i\le n，xi≤xi+1x_i\le x_{i+1}，并保证每种零件都至少有一个生产车间。

来源与许可

本题为 CQOI 2012 试题「组装」，题面与测试数据整理自 BZOJ。