题目背景

10s,2048M

题目描述

JOI 国是一个 $x\times y$ 的二维平面，王国里有 $n$ 个城镇，分别编号为 $1, 2, \cdots, n$，其中第 $i$ 个城镇的 坐标 为 $(x_i, y_i)$。

在 JOI 国，正计划修建连接两座城镇的路（下文简称：「修路的项目」），路有 $k$ 条。连接两个不同的城镇 $a$ 和 $b$ 将花费 $|x_a − x_b| + |y_a − y_b|$ 元。若有一条连接 $c$，$d$ 的路，则不需要也不可以在建一条连接 $d$，$c$ 的路，因为它们是相同的。

你要管理这个「修路的项目」，为了计算花费情况，你得弄明白连接一些城镇所需的花费。在这 $\dfrac{n\cdot(n-1)}{2}$ 条道路中，你想了解最便宜的 $k$ 条道路的花费。

给你城镇的坐标以及 $k$，请计算最便宜的 $k$ 条路所需要的钱。

输入格式

输入数据共 $n+1$ 行。

第一行，$2$ 个正整数 $n, k$，$n$ 表示城镇的数量，$k$ 含义见 「题目描述」 部分。

接下来的第 $2 \sim n+1$ 行，每行 $2$ 个正整数，分别是 $x_i$ 和 $y_i$，其中 $1\le i \le n$，表示第 $i$ 个城镇的坐标。

输出格式

输入数据共 $k$ 行。

对于第 $k$ 行，有一个整数表示第 $k$ 便宜的路需要的日元。

3 2
-1 0
0 2
0 0

1
2

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

2
2
3
3

4 6
0 0
1 0
3 0
4 0

1
1
2
3
3
4

10 10
10 -8
7 2
7 -8
-3 -6
-2 1
-8 6
8 -1
2 4
6 -6
2 -1

3
3
4
5
6
6
6
7
7
7

提示

样例 #1 解释

有 $\dfrac{3 \times 2}{2} = 3$ 种方案。

• 城镇 $1 \to$ 城镇 $2$，$|(-1)-0|+|0-2| = 3$ 日元。
• 城镇 $1 \to$ 城镇 $3$，$|(-1)-0|+|0-0| = 1$ 日元。
• 城镇 $2 \to$ 城镇 $3$，$|0-0|+|2-0| = 2$ 日元。

将其进行排序为 $1,2,3$，所以输出是 $1$ 和 $2$。

本样例满足 Subtask $1, 4, 5, 6$。

样例 #2 解释

有 $\dfrac{5 \times 4}{2} = 10$ 种方案。

将钱数排序后是 $2, 2, 3, 3, 3, 3, 4, 4, 4, 4$。

本样例满足 Subtask $1, 4, 5, 6$。

样例 #3 解释

本样例满足 Subtask $1, 2, 4, 5, 6$。

样例 #4 解释

本样例满足 Subtask $1, 4, 5, 6$。

数据范围与约定

本题采用 Subtask 计分法。

Subtask	分值占比百分率	$n$	$k$	$y_i$
$1$	$5\%$	$\le 10^3$	/	/
$2$	$6\%$	/		$=0$
$3$	$7\%$		$=1$	/
$4$	$20\%$		$\le 10$
$5$	$27\%$		$\le 10 ^ 5$
$6$	$35\%$		/

注：斜线表示无特殊限制。

对于 $100\%$ 的数据：

• $2 \le n \le 2.5 \times 10^5$；
• $1 \le k \le \min(2.5\times 10^5,\ \dfrac{n\cdot(n-1)}{2}$)；
• $-10^9 \le x_i, y_i \le 10^9$，且 $1 \le i \le n$；
• $(x_i,y_i)\not = (x_j, y_j)$ 且 $1 \le i < j \le n$。

说明

本题译自 第２０回日本情報オリンピック 2020/2021春季トレーニング合宿 - 競技 2 - T2 日文题面。