Description

Xiaoyun and Xiaonan, two sisters, have liked playing Chinese Chess since childhood. Now, as masters of the game, they are no longer interested in ordinary Chinese Chess, so they begin to play various new games using the board and pieces.

Today the weather is clear and sunny, and they are going to play on an $n\times m$ board.

There are $k$ pieces and some blocked cells on the board. Let the top-left cell be $(1, 1)$ and the bottom-right cell be $(n, m)$. Parameters $a, b$ define the moves of all pieces: a piece at $(x, y)$ can move in one step to one of the eight cells $(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), (x - b, y - a)$. A piece can never jump out of the board or onto a blocked cell.

These $k$ pieces are identical. The goal is to move all pieces to specified cells in the minimum number of steps. During the moves, it is forbidden for multiple pieces to be on the same cell at the same time.

They have already found a plan with relatively few steps, but they are not sure whether it is optimal, so they ask you, as a programmer, for help.

Input Format

The first line contains five integers $n, m, k, a, b$ separated by spaces.

The next $n$ lines each contain a string of length $m$ describing the board, where . denotes a free cell and * denotes a blocked cell.

The next $k$ lines each contain two integers $x$ and $y$, giving the initial positions of the $k$ pieces.

The next $k$ lines each contain two integers $x$ and $y$, giving the target positions of the $k$ pieces.

Output Format

Output a single integer: the minimum number of steps needed to move all pieces to their target positions. The testdata guarantees that a solution exists.

1 8 2 2 0
.......*
1 1
1 3
1 5
1 7

4

Hint

[Sample explanation]

One feasible plan is as follows: the second piece jumps two steps to the right, then the first piece jumps two steps to the right, for a total of $4$ steps. Note that although the plan where the first piece jumps three steps to the right and then the second piece jumps one step to the right can also move all pieces to the target positions, the two pieces would simultaneously be at $(1, 3)$ at some moment, which violates the rules, so this plan cannot be used.

Constraints

• For $20\%$ of the testdata, $n\times m \le 20$.
• Additionally, for $10\%$ of the testdata, $n = 1$.
• For $100\%$ of the testdata, $1 \le n, m \le 100$, $1 \le k \le 500$.

Translated by ChatGPT 5