思路概述

把每个人看作图的一个点，若两人差别值 $|a_i-a_j|+|b_i-b_j|\le L$，就在两点之间连一条“必须同组”的边。这样图的每个连通块中的人都被强制在同一组里；而不同连通块之间可以自由合并或各自成组。

于是，当给定 $L$ 时，“至少能分成多少组”的下界正是该图的连通块个数 $cc(L)$。题目等价于：求最大的整数 $L$，使得 $cc(L)\ge k$。

注意 $L$ 增大只会增加边数、使连通块数不增反减，因此性质单调：若某个 $L$ 可行（$cc(L)\ge k$），则任意更小的 $L$ 也可行。于是可二分答案。

算法与实现

题目内容

小明的公司要进行集体活动，活动要求所有人员分组。

当前有 $n$ 个人，每个人的能力值为 $a_i$ ，性格值为 $b_i$，现在希望将这 $n$ 个人分成若干组，每个人只能在一个组内。

当然，分组是一个问题，我们定义两个人的“差别值”为能力值的差和性格值的差的绝对值之和，即 $|a_i-a_j|+|b_i-b_j|$。

在分组前，我们规定一个差别上限 $L$ ，如果两个人的差别值不超过 $L$ ，那么在分组结果中该两人一定会在同一组内（当然，即使两个人差别值超过 $L$ ，两个人还是可以在同一个小组，只是不超过 $L$ 的必须在一组）。

现在我们想知道，如果能将所有人分成至少 $k$ 个非空的小组，规定的差别上限最多为多少。

输入描述

第一行两个正整数 $n$ 和 $k$ ，表示人数和分组要求。

接下来两行每行 $n$ 个整数，表示 $a_1, a_2, ..., a_n$ 和 $b_1, b_2, ..., b_n$ 。

$2 ≤ k ≤ n ≤ 500, 1 ≤ a_i, b_i ≤ 10^5$

保证任意两个人的能力值或者性格值至少有一项不同。

注：由于 $k＞1$ ，所以答案一定不为无穷大。

输出描述

输出一个整数表示最大的差别上限。

样例1

输入

3 2
1 9 3
2 7 8

输出

7

说明

$1$ 和 $2$ 的差别值为 $9-1+7-2=13$,

$2$ 和 $3$ 的差别值为 $9-3+8-7=7$ ,

$1$ 和 $3$ 的差别值为 $3-1+8-2=8$ ，

故差别上限为 $7$ 时， $2$ 和 $3$ 必须在一组，$1$ 单独一组，此时有 $2$ 组。

而上限为 $8$ 时， $2$ 和 `$3$ 必须在一组，$1$ 和 $3$ 必须在一组，所以 $1,2,3$ 只能一起一组，此时只有一组，不满足要求。

故上限最多为 $7$ 。