← 返回题目列表

Codeforces · 185/E

E. 肥皂时间! - 2

中文机器翻译题面 查看原题

想象一下笛卡尔坐标系。有 k 个不同的点包含地铁站。人们可以立即从任何一个地铁站到达任何一个地铁站。也就是说,任意两个地铁站之间的换乘时间可以被认为等于零。您只能在地铁站之间出行,也就是说,您不能在路线中间、车站之间的某个地方离开地铁。

有n个矮人,用他们在平面上的坐标来表示。矮人们想聚在一起在飞机上的某个整数点观看肥皂剧。为此,他们选择了集合点并同时开始向那里移动。一秒钟内,矮人可以从点 (x, y) 移动到以下点之一:(x - 1, y)、(x + 1, y)、(x, y - 1)、(x, y + 1)。此外,矮人可以无限次地乘坐地铁(地铁会立即转移矮人)。矮人在移动时不会互相干扰(即矮人同时且彼此独立地移动)。

帮助矮人找到他们在某一点聚集所需的最短时间。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105; 0 ≤ k ≤ 105) — 相应地,矮人的数量和地铁站的数量。

接下来的 n 行包含矮人的坐标。第 i 行包含两个空格分隔的整数 xi 和 yi (|xi|, |yi| ≤ 108) — 第 i 个矮星的坐标。保证所有矮人都位于不同的点。

接下来的 k 行包含地铁站的坐标。第 t 行包含两个空格分隔的整数 xt 和 yt (|xt|, |yt| ≤ 108) — 第 t 个地铁站的坐标。保证所有地铁站都位于不同的地点。

输出

打印一个数字——所有矮人可以聚集在一起观看肥皂剧的最短时间。

示例

输入 #1

1 0
2 -2

输出 #1

0

输入 #2

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

输出 #2

6