|Author:||A. Baranov||Time limit:||1 sec|
|Input file:||input.txt||Memory limit:||256 Mb|
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 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 must contain a single integer — minimal number of moves.
If there is no solution, output − 1.
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
|No.||Input file (
||Output file (|