Description

There are $m$ production workshops on the number line that can produce parts. There are $n$ types of parts, numbered $1 \sim n$. The $i$-th workshop is located at coordinate $x_i$ and produces part type $p_i$ ($1 \le p_i \le n$). You need to build an assembly workshop at some position on the number line to assemble these parts. To minimize transportation cost, you need to minimize $\,$ $cost_1 + cost_2 + \ldots + cost_n$, where $cost_x$ denotes the minimum squared distance from the assembly workshop to any workshop that produces part type $x$.

Input Format

The first line contains two integers $n$, $m$, the number of part types and the number of production workshops. Each of the following $m$ lines contains two integers $x_i$ and $p_i$ ($1 \le p_i \le n$). The input is ordered from left to right by workshop position (i.e., $x_i \le x_{i+1}$; note that positions may repeat). It is guaranteed that every part type has at least one workshop producing it.

Output Format

Output a single line: the optimal location of the assembly workshop (it may coincide with a production workshop), rounded to four decimal places. It is guaranteed that the optimal location is unique.

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

2.0000

Hint

• Test points 1–4: $n \le 15$, $m \le 25$, $x_i \le 100$.
• Test points 5–10: $n \le 10^4$, $m \le 10^5$, $x_i \le 10^5$.

Translated by ChatGPT 5