AT_joisc2021_e 道路の建設案 (Road Construction)

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$ 条路所需要的钱。 接下来的第 $2 \sim n+1$ 行，每行 $2$ 个正整数，分别是 $x_i$ 和 $y_i$，其中 $1\le i \le n$，表示第 $i$ 个城镇的坐标。

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

输入数据共 $k$ 行。 对于第 $k$ 行，有一个整数表示第 $k$ 便宜的路需要的日元。 ## 样例 #1 ### 样例输入 #1 ``` 3 2 -1 0 0 2 0 0 ``` ### 样例输出 #1 ``` 1 2 ``` ## 样例 #2 ### 样例输入 #2 ``` 5 4 1 -1 2 0 -1 0 0 2 0 -2 ``` ### 样例输出 #2 ``` 2 2 3 3 ``` ## 样例 #3 ### 样例输入 #3 ``` 4 6 0 0 1 0 3 0 4 0 ``` ### 样例输出 #3 ``` 1 1 2 3 3 4 ``` ## 样例 #4 ### 样例输入 #4 ``` 10 10 10 -8 7 2 7 -8 -3 -6 -2 1 -8 6 8 -1 2 4 6 -6 2 -1 ``` ### 样例输出 #4 ``` 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$。 #### 数据范围与约定 对于 $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)。