说明

在 5013 年，jh05013 征服了欧亚大陆并建立了“jh 国”。“jh 国”涵盖了整个大陆，由于其幅员辽阔、人口众多，jh05013 计划将国家划分为若干个“区”以便高效治理。“jh 国”内有 $N$ 座房屋，每座房屋位于二维笛卡尔坐标系中的 $(x_i, y_i)$ 处。jh05013 在划分区域时遵循以下条件：

• 条件 1：每个区包含的房屋，其 $x$ 坐标必须位于某个特定范围内。（一个区可以包含所有房屋，也可以不包含任何房屋）
• 条件 2：每座房屋必须恰好属于一个区。
• 条件 3：区的数量最多为 $K$ 个。

欧亚大陆上存在多种种族、宗教和国家。为了避免争端，我们必须尽量减少各区的“分裂度”。一个区的分裂度定义为该区内最远两座房屋之间的距离。距离采用欧几里得度量计算。请帮助 jh05013 最小化所有区中分裂度的最大值。

输入格式

第一行包含两个由空格分隔的整数 $N$ 和 $K$。$N$ 表示房屋的数量，$K$ 表示区的数量上限。

接下来的 $N$ 行，每行包含两个由空格分隔的整数 $x_i$ 和 $y_i$，表示一座房屋位于 $(x_i, y_i)$。

输出格式

设所有区中分裂度的最大值的最小值为 $M$，请输出 $M^2$。

4 2
101 100
2 5
100 101
4 3

8

4 4
3 1
4 1
5 1
9 2

0

提示

数据范围

• $1 \le K \le N \le 250,000$
• 所有给定的位置互不相同。即，若 $i \ne j$，则 $x_i \ne x_j$ 或 $y_i \ne y_j$。
• $0 \le x_i, y_i \le 10^9$

翻译由 DeepSeek V3.2 完成