Problem B. Broken chessboard ≡

Statement

You are given a board of n × m cells, one of them is occupied by a chess knight. Some cells were removed from the board.

Your program must determine the minimal number of moves that a knight must perform to visit all cells of a given list in order, not visiting removed cells in the process.

On other words, given list of cells must be a subsequence of cells visited by the knight.

Input file format

Input file contains integers n and m — board size.

Next there is an integer P, followed by P pairs of integers (a_i, b_i) — coordinated of removed cells.

Next there is an integer L, followed by L pairs of integers (x_i, y_i) — coordinates of cells to visit (starting with initial position of the knight).

Output file format

Output file must contain a single integer — minimal number of moves.

If there is no solution, output −1.

Constraints

0 < |x_i+1 − x_i| + |y_i+1 − y_i|, 2 ≤ (n, m) ≤ 100,

0 ≤ (a_i, x_i) < n, 0 ≤ (b_i, y_i) < m,

0 ≤ P ≤ 5000, 2 ≤ L ≤ 100

Sample tests

5 5

4
2 3
4 3
2 4
1 1

3
3 1
1 2
0 3

5

5 5

4
2 2
4 3
2 4
1 1

3
3 1
2 3
0 3

-1