题目描述

数轴上有m个生产车间可以生产零件。一共有$n$ 种零件，编号为 $1-n$。第$i$ 个车间的坐标为$x_i$，生产第$p_i$ 种零件 $(1\le p_i\le n)$。你需要在数轴上的某个位置修建一个组装车间，把这些零件组装起来。为了节约运输成本，你需要最小化$cost_1+cost_2+...+cost_n$，其中 $cost_i$ 表示生产第x种零件的车间中，到组装车间距离的平方的最小值。

输入格式 输入第一行为两个整数$n, m$，即零件的种类数和生产车间的个数。以下$m$ 行每行两个整数$x_i$ , $p_i$。输入按照生产车间从左到右的顺序排列（即$x_i \le x_{i+1}$。注意车间位置可以重复）。输入保证每种零件都有车间生产。

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