A campground is represented as a grid where each square can contain a campsite that is either reserved or free. The distance between two squares $(x_1, y_1)$ and $(x_2, y_2)$ is the Manhattan distance $|x_1 - x_2| + |y_1 - y_2|$ .
Your task is to find the maximum distance from a free campsite to the nearest reserved campsite.
The first line has two integers $n$ and $m$ :
the number of reserved and free campsites.
The next $n$ lines describe the __cpLocations of the reserved campsites. Each line has two integers $x$ and $y$ .
The next $m$ lines describe the __cpLocations of the free campsites. Each line has two integers $x$ and $y$ .
You can assume that each square contains at most one campsite.
Print one integer: the longest distance to the nearest reserved campsite.
4 2 1 1 5 2 2 6 4 7 1 3 7 5· \n · \n · \n · \n · \n · \n · \n
5\n
In this case, the best choice is the free campsite on the right, whose distance to the nearest reserved campsite is $5$ .