Description

Chansu 是 ICPC 大学的一名研究生，正在实验室攻读硕士学位。他的研究主题是揭示特定群体 G 中个体肥胖程度与年收入之间的关系。

Chansu 从 G 中的 $n$ 个人收集了形式为 $(x_i, y_i)$ 的数据，其中 $x_i$ 和 $y_i$ 分别表示第 $i$ 个人的肥胖指数和年收入，并提出了一个初步假设：

群体 G 中个体的肥胖程度与年收入之间存在线性依赖关系。

为了证明他的假设，Chansu 试图找到一个具有实系数的最优线性函数 $f^*(x)$，使得相对于收集数据的误差最小。更具体地说，函数 $f$ 相对于数据的误差定义为所有 $i = 1, \dots, n$ 中 $|y_i - f(x_i)|$ 的最大值。

然而，结果令人失望，因为最优函数 $f^*(x)$ 的误差出乎意料地大。这意味着他的假设无法通过这种方式得到证明。

Chansu 试图找出大误差的原因。有一天，他将数据 $(x_i, y_i)$ 绘制为坐标平面上的点，并意识到有少数 $k$ 个点异常远离其他点，因此移除这些点后，最优函数的误差可以大幅减小。

作为 Chansu 的朋友，你非常乐意帮助他。请编写一个程序，在给定允许从数据 $\{(x_1, y_1), \dots, (x_n, y_n)\}$ 中移除 $k$ 个值（$k$ 作为输入的一部分给出）的情况下，找到最小化误差的最优线性函数，并输出误差值。

Input Format

你的程序需要从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $k$ ($1 \leq n \leq 50,000$, $0 \leq k \leq \min\left\{\frac{n}{2}, 300\right\}$)，其中 $n$ 是收集的数据值的数量。接下来的 $n$ 行中，每行给出一个数据值 $(x_i, y_i)$，由两个整数 $x_i$ 和 $y_i$ 表示 ($-10^9 \leq x_i, y_i \leq 10^9$)，对应 $i = 1, \dots, n$。你可以假设当将这些点绘制在坐标平面上时，没有三点共线。

Output Format

你的程序需要向标准输出写入数据。输出恰好一行。该行应包含一个实数 $z$，表示在移除 $k$ 个值后，线性函数相对于数据的最小可能误差。你的输出 $z$ 应以整数部分、小数点和小数部分的格式给出，如果满足 $a - 10^{-6} < z < a + 10^{-6}$，则将被判定为“正确”，其中 $a$ 表示精确答案。

6 0
0 0
5 -1
9 6
3 0
4 2
3 1

2.166667

6 1
0 0
5 -1
9 6
3 0
4 2
3 1

1.000000

6 2
0 0
5 -1
9 6
3 0
4 2
3 1

0.500000

6 3
0 0
5 -1
9 6
3 0
4 2
3 1

0.083333

Hint

翻译由 DeepSeek V3 完成