该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在二维平面上的 塔尖 村庄里有 $N$ 个房屋。每个第 $i$ 个房屋的位置是 $(X_i, Y_i)$。

第 $i$ 个房屋和第 $j$ 个房屋之间的距离是 $|X_i − X_j| + |Y_i − Y_j|$，也就是两个房屋之间的距离是 X 坐标差和 Y 坐标差的和。例如，位于 $(1, 6)$ 的房屋与位于 $(2, 4)$ 的房屋之间的距离是 $(2 - 1) + (6 - 4) = 3$。

塔尖 村庄计划在发生灾难时，在 $K(K\leq 3)$ 个房屋里安装避难所，以便居民能够安全撤离。为了考虑所有居民的安全，计划选择 $K(K\leq 3)$ 个房屋作为避难所，使得每个居民到达最近避难所的距离尽可能小，其中最远的距离要尽量小。

以下是 $5$ 个房屋的位置，分别是 $(1, 5)$、$(3, 0)$、$(3, 3)$、$(6, 12)$ 和 $(8, 9)$。

在这个村庄里，计划安装 $2$ 个避难所。如果我们将避难所分别安装在 $(3, 0)$ 和 $(1, 5)$ 位置，剩下的 $3$ 个房屋到最近避难所的距离分别是 $3$、$11$、$12$，其中最远的距离是 $12$。

但是，如果将避难所安装在 $(3, 3)$ 和 $(6, 12)$ 位置，最远的距离是 $5$，即位于 $(8, 9)$ 的房屋到 $(6, 12)$ 的距离为 $5$。

无论如何安装避难所，最远的距离无法小于 $5$，因此我们要找出最小的最大距离。

给定 塔尖 村庄中房屋的位置和安装避难所的数量，要求你输出在所有可能的安装方案中，最近的避难所和房屋之间的距离的最大值最小的情况下的最大距离。

输入格式

第一行包含两个整数 $N$ 和 $K(K\leq 3)$，表示房屋的数量和避难所的数量。

接下来 $N$ 行，每行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个房屋的坐标。

输出格式

输出一个整数，表示最小的最大距离。

5 2
1 5
3 0
3 3
6 12
8 9

5

4 2
0 0
0 5
5 0
5 5

5

4 1
1 0
2 0
3 0
4 0

2

2 1
20 23
5 14

24

提示

数据范围

• 所有输入的数值均为整数。
• $1 \leq K \leq 3$，$K \leq N \leq 50$
• $0 \leq X_i,Y_i \leq 100,000$
• 同一位置上不会有多个房屋，即 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ 都是不同的。