## Problem B. Broken chessboard ≡

• problems
• en ru
 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.092s 0.009s 15