CF185E Soap Time! - 2

想象一个笛卡尔坐标系。有 $k$ 个不同的点上建有地铁站。从任意一个地铁站可以瞬间到达其他任意地铁站，也就是说，任意两个地铁站之间的传送时间可以视为 $0$。你只能在地铁站之间搭乘地铁，即你不能在两个地铁站之间的中间某处下车。 有 $n$ 个小矮人，他们在平面上的坐标分别给出。这些小矮人想聚集到某个整数点上一同观看肥皂剧。为此，他们需要选择一个聚集点并同时出发前往。每秒钟，小矮人可以从点 $(x,y)$ 移动到以下任一相邻点：$(x-1,y)$、$(x+1,y)$、$(x,y-1)$、$(x,y+1)$。此外，小矮人可以不限次数地使用地铁（地铁传送是瞬间完成的）。小矮人在运动过程中不会互相干扰（即小矮人是同时且独立地移动的）。 请你帮助小矮人们，计算他们全部聚集到一个点所需的最少时间。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^{5};\ 0 \leq k \leq 10^{5}$），分别表示小矮人的数量和地铁站的数量。 接下来的 $n$ 行每行包含两个用空格分隔的整数 $x_i$ 和 $y_i$（$|x_i|,|y_i| \leq 10^{8}$），表示第 $i$ 个小矮人的坐标。保证所有小矮人都位于不同的位置。 接下来的 $k$ 行，每行包含两个用空格分隔的整数 $x_t$ 和 $y_t$（$|x_t|, |y_t| \leq 10^{8}$），表示第 $t$ 个地铁站的坐标。保证所有地铁站都位于不同的位置。

输出一个整数，表示所有小矮人聚集到同一点所需的最少时间。

由 ChatGPT 5 翻译