Перед Вами разворачиваются драматические события – старый паук сидел на своей прямоугольной паутине, как вдруг она загорелась в некоторых местах. К счастью, предусмотрительный паук приготовил специальную клетку, с которой он сможет эвакуироваться. Теперь его задача – добраться до этой клетки. При этом он стремиться пробежать по самому безопасному пути.

Паутина представляет собой прямоугольную сетку (1, 1) - (a, b). Известны точки поджога. Начальное положение паука – (1, 1). Точка эвакуации (a, b). Паук перемещается по ребру сетки за 1 секунду, а огонь за t секунд. Паук не может находиться в горящей вершине.

Введем понятие опасности пути. Рассмотрим некоторый путь. Назовем вершину пути опасной, если в момент прохождения этой вершины хотя бы одна смежная к ней вершина горит. Опасностью пути назовём количество опасных вершин в нём. Паук хочет обеспечить себе максимальную безопасность. Помогите ему!

Входные данные

В первой строке запданы числа a и b (1 ≤ a, b ≤ 500) - размеры паутины. В следующей строке находится число t (1 ≤ t ≤ 100). Седующая строка содержит число k (1 ≤ k ≤ a * b) – количество точек поджога. В каждой из следующих k строк находятся два числа - координаты поджигаемых вершин.

Выходные данные

Выведите минимальную опасность пути из (1, 1) в (a, b). Если такого пути нет - выведите "-1".

Пояснение

В первом тесте паук идёт по пути (1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3) → (4, 3). Опасной изначально является клетка (1, 1) – рядом с ней находиться горящая (2, 1). Когда паук находится в клетке (1, 2), горит всё ещё только клетка (2, 1), поэтому (1, 2) не опасная. Когда паук попадает в (1, 3), загораются еще три клетки - (1, 1), (2, 2), (3, 1), но ни одна из горящих не граничит с (1, 3), поэтому она не опасна. Далее паук в клетке (2, 3), клетка (2, 2) горит, значит (2, 3) опасная. Когда паук приходит в (3, 3), загораются ещё клетки: (1, 2), (2, 3), (3, 2), (4, 1). Видно, что (3, 3) - смежная с (3, 2), которая уже горит, значит (3, 3) опасная. Когда следующим перемещением паук оказывается в клетке (4, 3), новые клетки не зажигаются (еще не прошло две секунды), а ни одна из горящих не граничит с (4, 3). Следовательно, опасность пути равна 3 (три опасные вершины – (1, 1), (2, 3) и (3, 3)). Никаким другим путём паук не сможет приползти, не пройдя по горящим клеткам.

Во втором случае после трёх секунд загорается вершина (4, 3), а паук никак не успеет добраться до неё за три секунды.