题目描述

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

输入格式

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

输出格式

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

说明/提示

对于 $40\%$ 的数据，满足 $n\le 15,m\le25,x_i\le100$

对于 $100\%$ 的数据，满足 $n\le 10^4,m\le 10^5,x_i\le10^5$

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

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

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

### 说明/提示

对于 $40\%$ 的数据，满足 $n\le 15,m\le25,x_i\le100$

对于 $100\%$ 的数据，满足 $n\le 10^4,m\le 10^5,x_i\le10^5$