链接: https://cses.fi/problemset/task/3306

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一个露营地表示为一个网格，其中每个方格可以包含一个营地，该营地要么已被预订，要么空闲。两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离是曼哈顿距离 $|x_1 - x_2| + |y_1 - y_2|$。

你的任务是找出从一个空闲营地到最近的已预订营地的最大距离。

输入

第一行包含两个整数 $n$ 和 $m$：已预订和空闲营地的数量。

接下来的 $n$ 行描述已预订营地的位置。每行有两个整数 $x$ 和 $y$。

接下来的 $m$ 行描述空闲营地的位置。每行有两个整数 $x$ 和 $y$。

你可以假设每个方格至多包含一个营地。

输出

输出一个整数：到最近的已预订营地的最长距离。

数据范围

$1 \le n, m \le 10^5$ $1 \le x, y \le 10^6$

样例输入

4 2
1 1
5 2
2 6
4 7
1 3
7 5

样例输出

5