[JOISC 2021 Day2] 道路の建設案 (Road Construction)

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春季トレーニング合宿 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [競技 2 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day2/2021-sp-d2-notice.pdf) [T2 日文题面](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day2/road_construction.pdf)。