[cqoi2012]组装

数轴上有 $m$ 个生产车间，共生产 $n$ 种零件，零件编号为 $1\sim n$。第 $i$ 个生产车间的坐标为 $x_i$，生产第 $p_i$ 种零件，其中 $1\le p_i\le n$。

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

$$\sum_{k=1}^{n}\operatorname{cost}(k)。$$

输入格式

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

接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $p_i$，分别表示第 $i$ 个生产车间的坐标及其生产的零件种类，其中 $1\le p_i\le n$。

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

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

输出格式

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

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

样例输入

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

样例输出

2.0000

数据范围

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

来源与许可

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

样例 1

输入

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

输出

2.0000