|
Лимит времени 500/500/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Problem description
На клеточном поле, размером NxM (2 ≤ N, M ≤ 1000) сидит Q (0 ≤ Q ≤ 10000) блох в различных клетках. «Прием пищи» блохами возможен только в кормушке – одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.
Input
Входной файл содержит в первой строке 5 чисел, разделенных пробелом: N, M, S, T, Q.
N, M – размеры доски (отсчет начинается с 1); S, T – координаты клетки - кормушки (номер строки и столбца соответственно), Q – количество блох на доске. И далее Q строк по два числа – координаты каждой блохи.
Output
Выходной файл Output.txt должен содержать одно число – минимальное значение суммы длин путей или –1, если сбор невозможен.
Example
| stdin |
stdout |
4 4 1 1 3
2 3
3 2
3 3 |
6 |
| 5 5 3 4 0 |
0 |
Для отправки решений необходимо выполнить вход.
|