Xiao Yun and Xiao Nan are sisters who have loved playing chess since they were young. Now, as chess experts, they find ordinary chess boring, so they have started playing various new games using chessboards and pieces.
Today is a sunny and bright day, and they are going to play a game on an $n \times m$ chessboard.
There are $k$ pieces and several obstacle squares on the board. Let the coordinates of the top-left square be $(1, 1)$ and the bottom-right square be $(n, m)$. Parameters $a$ and $b$ define the movement of all pieces: a piece at $(x, y)$ can move to one of the following eight squares in the next step: $(x + a, y + b)$, $(x + a, y - b)$, $(x - a, y + b)$, $(x - a, y - b)$, $(x + b, y + a)$, $(x + b, y - a)$, $(x - b, y + a)$, or $(x - b, y - a)$. A piece cannot move off the board or onto a square with an obstacle at any time.
The $k$ pieces are identical. Xiao Yun and Xiao Nan's goal is to move all pieces to specific target squares in the minimum number of steps, with the requirement that no two pieces can occupy the same square at the same time during the movement process.
They have come up with a solution with a relatively small number of steps, but they cannot determine if it is the minimum number of steps, so they are asking you, the programmer, for help.
Input
The first line contains five space-separated integers $n$, $m$, $k$, $a$, and $b$.
The next $n$ lines each contain a string of length $m$ describing the chessboard, where '.' represents a square without an obstacle and '*' represents a square with an obstacle.
The next $k$ lines each contain two integers $x$ and $y$, representing the initial positions of the $k$ pieces.
The next $k$ lines each contain two integers $x$ and $y$, representing the target positions of the $k$ pieces.
Output
A single integer representing the minimum number of steps to move all pieces to the target positions. It is guaranteed that a solution exists.
Examples
Input 1
1 8 2 2 0 .......* 1 1 1 3 1 5 1 7
Output 1
4
Note
One feasible solution is as follows: the second piece jumps two steps to the right, and then the first piece jumps two steps to the right, for a total of 4 steps. It is worth noting that the solution where the first piece jumps three steps to the right and then the second piece jumps one step to the right, although it can move the pieces to the target positions, violates the rules because the two pieces were once at $(1, 3)$ at the same time, so this solution cannot be used.
Constraints
For 20% of the data, $n \times m \le 20$.
For another 10% of the data, $n = 1$.
For 100% of the data, $n, m \le 100$, $k \le 500$.