Processing math: 100%

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+1xi|+|yi+1yi|, 2(n,m)100,

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

0P5000, 2L100

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.066s 0.008s 15