Knight Match Play

There are two knight teams, they have N and M knights respectively. The knights are numbered from 1 to N and 1 toM in their own team. They are trapped in an W*H grid puzzle. The puzzle only has four exituses which are the four corners of the puzzle. Only the directions up,down,left, right could the knight move to and the time move from one grid to the adjacent is fixed. They can form a "fight partner" if two knights sufficing the following conditions:

1. The two knights come from different teams.

2. Both of them can arrive to one of the exituses.

3. The least time need to arrive to one of the exituses is same.

So how many "fight partners" they can form?

For this action, the leader gives the follow directives:

1. Each team renumbering the knights with their least time need to use to get out of the puzzle. So the one who use the least time will get the ID 1 and the one use the most time will get the ID N or M. If some of them use the same time, then whose original ID is lower, who will get a lower ID.

2. The chosen knights from the same team should have the continuous ID.

3. Form "fight partners" according to the IDs one by one. That is to say the one has the lowest ID should form with the one has the lowest ID in another team, and so on.

Input

There are several test cases.The input of every test case are described as below.

First line, there are four integers N, M, W, H. (0 < N, M < 300, 10 < W, H < 50).

Then there are H lines, each line with W characters indicate for the puzzle.A character of '.' indicate the grid is empty, every empty grid could contain infinitely of knights. A character of '#' means the grid has a barrier and none knight can step into it. The four corners are empty.

Then there N+M lines, each line with a pair of integers (x, y) (0 ≤ x < H, 0 ≤ y < W) indicate for the knight is in thex^th line and y^th column originally.

The input will finish with the end of file.

Output

An integer indicate for the maximal number of "fight partner" they can form.

Examples