Problem: Pam-Can Retires

Want to try solving this problem? You can submit your code online if you log in or register.

Pam-Can Retires

Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 256 MB

After spending the last thirty-five years roaming maze after maze and fleeing from ghosts and goblins you - the once world famous PAM-CAN - have decided to retire somewhere in the blissful estate known only as Level 257.

Level 257 is a grid of cells with R rows and C columns. The rows are numbered 1 to R from top to bottom and columns are numbered 1 to C from left to right. Every cell is either blocked off by uninhabitable mountains (a block cell), contains fruit (a fruit cell) or is completely empty.

You resolve to pick precisely one of these cells as your retirement cell. This cell should either be a fruit cell or completely empty - it cannot be a block cell. From it, you may be able to see other grid cells. Specifically, a cell is visible from your retirement cell if and only if:

The cell is either in the same row or in the same column as your retirement cell; and
There are no block cells on the straight line between the cell and your retirement cell.

Note that your retirement cell is always visible from itself. The diagram below shows a possible layout for Level 257 (on the left) and all visible cells (shaded) if you choose your retirement cell to be at row 1, column 4 on the grid (on the right).

$\includegraphics{pamcan-sample1.eps}$

As you ponder your future you ask yourself: "What is the maximum number of fruit cells that could be visible from my retirement cell?" You shudder at the thought of never seeing your beloved fruit again so you decide to write a program to answer this question for you.

Input

The first line of input will contain one line with four space-separated integers R C B F, representing the number of rows and columns in the grid, respectively, and the number of block cells and fruit cells in the grid, respectively.
The following B lines of input will each contain two space-separated integers describing the row and column of a block cell.
The following F lines of input will each contain two space-separated integers describing the row and column of a fruit cell.

Every cell will be described at most once in the input. Every cell that is not described in the input is completely empty.

Output

Your program must output a single integer: the maximum number of fruit cells that are visible from a valid retirement cell. You are guaranteed that there is at least one valid retirement cell in every testcase.

Sample Input

Sample Output

Explanation

If you retire to row 1, column 4, you will be able to see the fruit at coordinates (1,3),(1,5),(2,4),(4,4) for a total of 4 fruit. Note that you will not be able to see the fruit at location (1,1) as it is blocked by location (1,2). No other square can see more fruit, therefore the answer is 4.

Subtasks & Constraints

For all subtasks, 1 ≤ R, C ≤ 100,000 and 0 ≤ B + F ≤ 100,000. Additionally, all cells have a row number between 1 and R (inclusive) and a column number between 1 and C (inclusive).

For Subtask 1 (10 points), 1 ≤ R, C ≤ 100.
For Subtask 2 (50 points), 1 ≤ R, C ≤ 1,000.
For Subtask 3 (15 points), B = 0. That is, there are no block cells.
For Subtask 4 (25 points), no further constraints apply.