Data Analysis

Alice, a data scientist, is asked to analyze data. Each data point is a 2D coordinate $(x, y)$.

The analysis finds $K$ line segments parallel to the $x$-axis in the 2D plane. Specifically, you must determine the following values.

• The $x$-coordinates of the segment endpoints $0=p_0 < p_1 < \cdots < p_K = 50\ 000$. The endpoints of the $i$-th segment are $p_{i-1}$ and $p_i$. Here $1 \leq i \leq K$.
• The $y$-coordinates of the segments $m_1, m_2, \cdots, m_K$.

You cannot choose the values of $m_1, \cdots, m_K$ arbitrarily. To improve accuracy, an error is defined, and the values are chosen to minimize it. The error is defined as follows.

• The error of a data point $(x, y)$ is $|y - m_i|$, where $i$ satisfies $p_{i-1} \leq x < p_i$.
• The total error is the sum of the errors of all data points.

Alice wants to choose $p_0, \cdots, p_K$ and $m_1, \cdots, m_K$ so that the error is minimized. Find the minimum possible error when these values are chosen appropriately.

The first line contains the number of data points $N$ and the number of segments to find $K$, separated by a space.

The next $N$ lines each contain a data point $(x, y)$, separated by a space. All $x$ values are distinct.

Print the minimum analysis error when $p_0, \cdots, p_K$ and $m_1, \cdots, m_K$ are chosen appropriately. An absolute or relative error of up to $10^{-4}$ is accepted.

• The input values are all integers.
• $1\leq N \leq 3\,000$
• $1\leq K \leq \min(N, 10)$
• $0\leq x < 50\,000$
• $0\leq y \leq 1\,000$