Problem D
That Sinking Feeling

We expect you will never be bored in the Masters Program in Computer Science but, in case you’re ever in need of entertainment, how about a nice little game of Battleship? We will be playing an alternate version of the game where you win points for sinking your opponent’s ships, but also for firing a shot close to a ship.

More specifically, we will assume an $N$ by $M$ board, where the bottom-left square is the $(0,0)$ square, and that the x coordinate increases as you move right, and the y coordinate increases as you move up.

For example, a board with $N=6$ and $M=5$ would look like this:

One player can place any number of ships on the board. Unlike Battleship, each ship occupies a single square. There are no ships that span multiple squares. For example, if the player placed ships in squares $(4,3)$, $(2,4)$, $(1,2)$, and $(3,1)$, the board would look this this:

The other player starts off with zero points, and can fire a finite number of shots at any square of the board to earn more points. The number of points depends on the location of the shot:

• If a shot hits a ship, and the ship had not previously been sunk, then the ship sinks, and the player wins $1000$ points.

• If a shot hits water, the player wins

  \[ \max (0, 1000 - D\cdot 100) \]

  points, where $D$ is the Manhattan Distance to the nearest non-sunken ship. The Manhattan Distance (also known as rectilinear distance or taxicab distance) between two points is the sum of the absolute differences of their Cartesian coordinates.

  The scoring formula means that the player will earn more points the closer the shot is fired to a ship, but without resulting in negative points (if the shot is too far away).

For example, given the above board, let’s assume the player is allowed two shots. The player chooses square $(2,4)$ followed by $(0,1)$. This would result in a hit and a miss, respectively:

The hit would earn the player $1000$ points, and the miss would earn the player 800 points: the nearest ship is the one in $(1,2)$, and the Manhattan Distance between $(1,2)$ and $(0,1)$ is 2:

Let’s say the player was allowed a third shot, and chose (0, 4):

In this case, even though the ship at $(2,4)$ is the nearest one, it has already been sunk, so it does not count. Instead, the nearest ship is the one at $(1,2)$. The Manhattan Distance between $(0,4)$ and $(1,2)$ is 3:

So the miss earns the player an additional 700 points ($1000 - 3\cdot 100$).

Your program will take a list of ships and shots on a board, and will compute the final score of the game.

Input

The input contains the specification of a single game. The first line contains four positive integers: $N$, $M$, $S$, $R$ (each separated by a single space). $N$ and $M$ specify the size of the board, as described earlier. $S$ is the number of ships on the board, and $R$ is the number of shots fired. You may assume the following bounds:

Next, there are $S+R$ lines, specifying the coordinates on the board of the ships and shots. The first $S$ lines specify the ships, and the remaining $R$ lines specify the shots. The coordinates of each ship/shot is specified by two non-negative integers (the x and y coordinates) separated by a single space.

Output

You must print $H$/$S$ ships sunk. Score: $P$ points, where $H$ is the number of ships sunk, $S$ is the total number of ships, and $P$ is the final score.

Note that the two games in the sample data correspond to the examples shown earlier.

6 5 4 2
4 3
2 4
1 2
3 1
2 4
0 1

1/4 ships sunk. Score: 1800 points

6 5 4 3
4 3
2 4
1 2
3 1
2 4
0 1
0 4

1/4 ships sunk. Score: 2500 points