#4607. 3491. 「JOISC 2021 Day2」道路建设

3491. 「JOISC 2021 Day2」道路建设

Description

题目译自 JOISC 2021 Day2 T2「道路の建設案 / Road Construction

JOI 王国坐落于一个 xyxy 平面上,王国里有 NN 座小城,分别编号为 1N1\ldots N,其中第 ii 个小城的坐标为 (Xi,Yi)(X_i, Y_i)

现在王国正筹划着在小城之间建 KK 条路,而连接两个不同的小城 iijj 将花费 XiXj+YiYj|X_i-X_j|+|Y_i-Y_j| 元。在这里我们认为「连接小城 iijj」和「连接小城 jjii」本质相同。

和往常一样,你成为了这个项目的主管。为了估算花费情况,你想了解连接一些小城所需的花费。在这 N(N1)2\frac{N(N-1)}{2} 条可能的道路中,你想了解最便宜的 KK 条道路的花费。

你的任务是,给出小城的坐标以及 KK 值,编写一个程序计算最便宜的 KK 条道路的花费。

Input

第一行两个整数 NN, KK

接下来 NN 行每行两个整数 Xi, YiX_i,~Y_i

Output

输出 KK 行,第 kk 行为第 kk 便宜的道路价格。

Samples

3 2 
-1 0 
0 2
0 0
1
2

小城 1, 2, 31,~2,~3 的坐标分别为 (1, 0), (-1,~0),~(0,2), (0,2),~(0,0)(0,0),有 3×22=3\frac{3\times 2}{2}=3 种道路。

  • 在小城 1122 之间建设道路花费 (1)0+02=3|(−1) − 0| + |0 − 2| = 3 元。
  • 在小城 1133 之间建设道路花费 (1)0+00=1|(−1) − 0| + |0 − 0| = 1 元。
  • 在小城 2233 之间建设道路花费 00+20=2|0 − 0| + |2 − 0| = 2 元。

建设道路的价格从便宜到贵分别是 1, 2, 31,~2,~3。因此第一行输出 11,第二行输出 22。 本输入满足子任务 1,4,5,61, 4, 5, 6 的条件。

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

N=5N=5 知有 5×42=10\frac{5\times 4}{2}=10 种道路。

建设道路的价格从便宜到贵分别是 2,2,3,3,3,3,4,4,4,42, 2, 3, 3, 3, 3, 4, 4, 4, 4。因此,前 44 便宜的道路价格为 2,2,3,32, 2, 3, 3

本输入满足子任务 1,4,5,61, 4, 5, 6 的条件。

4 6
0 0
1 0
3 0
4 0
1
1
2
3
3
4

本输入满足子任务 1,2,4,5,61, 2, 4, 5, 6 的条件。

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,4,5,61, 4, 5, 6 的条件。

Limitation

1s, 1024KiB for each test case.