k_35P likes to play with magnets. He has placed magnets on the floor at integral coordinates, and will soon drop metal pieces. When dropped onto a floor, pieces of this metal will always land at integral coordinates, as if the floor was an infinitely large Cartesian Plane.
Upon reaching the floor, a metal piece will also immediately move to the nearest (as per Manhattan distance) floor tile which has a magnet on it — the magnets do not move. If a metal piece is equidistant to two or more magnets that are tied for closest distance, it will not move, even if the magnets are at the same coordinates.
Before k_35P drops any metal, however, he's allowed you to place exactly one additional magnet at any integral coordinate on the floor (including directly under a tile where a piece of metal will land). You want to place this magnet such that it will collect as many pieces of metal as possible. Unable to solve this problem by hand, you've decided to write a program to determine the maximum number of metal pieces that your magnet can collect, if placed optimally.
The Manhattan distance between a given point and another point is defined as .
For 40% of the points, .
For an additional 10% of the points, .
For all cases, .
The first line will contain .
In the next lines, line will contain two space-separated integers and , indicating the coordinates of the -th magnet.
The next line will contain a single integer .
For the next lines, line will contain two space-separated integers and , indicating the coordinates where the -th piece of metal will be dropped.
A single integer, the maximum number of metal pieces you can collect by placing a single magnet.
Sample Input 1
1 0 0 2 0 1 1 0
Sample Output 1
Explanation for Sample Output 1
A magnet can be placed either directly where the first piece of metal will fall, or the second. Placing it anywhere else will result in it collecting no metal, as both pieces of metal are unit away from the magnet already set up.
Sample Input 2
3 0 0 10 0 5 5 3 3 0 5 2 7 0
Sample Output 2
Explanation for Sample Output 2
Place a magnet at , which will be units away from all metal pieces. Since each piece is units away from the nearest magnet, all can be collected by placing it here.
Sample Input 3
1 9 21 3 0 14 18 33 21 19
Sample Output 3