Задача B. Broken chessboard ≡

Условие

Имеется доска размером n × m клеток, в одной из которых расположен шахматный конь. При этом часть клеток предварительно была удалена с доски.

Требуется определить минимальное число ходов, которое необходимо затратить коню, чтобы последовательно посетить все клетки заданного списка, не проходя при этом через удалённые клетки.

Иными словами, заданный список клеток должен являться подпоследовательностью посещённых конём клеток.

Формат входного файла

Входной файл содержит целые числа n и m — размеры доски.

Далее идёт целое число P, за которым следует P пар целых чисел (a_i, b_i) — координаты удалённых клеток.

Далее идёт целое число L, за которым следует L пар целых чисел (x_i, y_i) — координаты клеток, через которые необходимо пройти (включая начальное местоположение коня).

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальное количество ходов.

Если задача не имеет решения, следует вывести −1.

Ограничения

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

Примеры тестов

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