Problem B. Broken chessboard

Author:A. Baranov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

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 (ai, bi) — coordinated of removed cells.

Next there is an integer L, followed by L pairs of integers (xi, yi) — 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 < |xi + 1 − xi| + |yi + 1 − yi|, 2 ≤ (n, m) ≤ 100,

0 ≤ (ai, xi) < n, 0 ≤ (bi, yi) < m,

0 ≤ P ≤ 5000, 2 ≤ L ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 5

4
2 3
4 3
2 4
1 1

3
3 1
1 2
0 3
5
2
5 5

4
2 2
4 3
2 4
1 1

3
3 1
2 3
0 3
-1

0.160s 0.019s 15