데이터 분석

데이터 과학자 앨리스는 데이터를 분석하는 일을 받았다. 각 데이터는 2차원 좌표 $(x, y)$로 구성된다.

데이터 분석은 $x$축에 평행한 $K$개의 선분을 2차원 상에서 찾는 과정이다. 구체적으로 아래의 값들을 결정해야한다.

각 선분의 끝을 나타내는 $x$좌표 $0=p_0 < p_1 < \cdots < p_K = 50\ 000$, $i$번째 선분의 양 끝은 $p_{i-1}$과 $p_i$이다. $1 \leq i \leq K$
각 선분의 $y$좌표 $m_1, m_2, \cdots, m_K$

물론 $m_1, m_2, \cdots, m_k$의 값들을 아무렇게나 결정하면 안 된다. 분석의 정확도를 높이기 위해서, 분석의 오차를 정의한 다음 오차가 최소가 되도록 값을 결정해 줄 것이다. 오차는 다음과 같이 정의한다.

앨리스는 데이터 분석의 오차가 최소가 되도록 $p_0, \cdots, p_k$와 $m_1, \cdots, m_k$를 결정하고자 한다. 각 값을 적절히 결정했을 때, 데이터 분석의 오차의 최솟값을 구하시오.

첫 번째 줄에 데이터의 개수 $N$과 찾아야하는 선분의 개수 $K$가 공백으로 구분되어 주어진다.

이후 $N$개의 줄에 각 데이터 $(x, y)$가 공백으로 구분되어 주어진다. 단, 모든 데이터의 $x$ 값은 다르다.

데이터 분석의 오차가 최소가 되도록 $p_0,\cdots, p_k$와 $m_1,\cdots, m_k$의 값을 적절히 결정했을 때, 데이터 분석의 오차를 출력한다. 절대/상대 오차는 $10^{-4}$까지 허용한다.