Євакуація#4370

Євакуація

2 секунди

128 мегабайтів

Середня

Перед вами розгортаються драматичні події — старий павук відпочивав на своїй прямокутній павутині, як раптом у деяких її місцях спалахнула пожежа. На щастя, передбачливий павук підготував спеціальну клітинку для евакуації. Тепер його завдання — дістатися до цієї клітини якнайбезпечнішим шляхом.

Павутина — це прямокутна сітка з координатами від $(1, 1)$ до $(a, b)$ . Відомо, у яких клітинах спалахне пожежа. Павук починає у клітині $(1, 1)$ , а евакуаційний пункт розташований у $(a, b)$ . Павук переміщується по ребрах сітки за $1$ секунду, а вогонь поширюється кожні $t$ секунд. Павук не може знаходитися у клітині, в якій горить вогонь.

Визначимо поняття небезпеки шляху: під час руху павука через певну клітинку назвемо її небезпечною, якщо в цей момент хоча б одна суміжна до неї клітинка горить. Небезпека шляху — це кількість небезпечних клітин, через які проходить павук. Павук прагне мінімізувати цю кількість. Допоможіть йому знайти найбезпечніший маршрут!

Вхідні дані

У першому рядку записано два числа $a$ і $b$ ( $1 \leq a, b \leq 500$ 1 \leq a, b \leq 500) — розміри павутини. У другому рядку знаходиться $t$ ( $1 \leq t \leq 100$ 1 \leq t \leq 100) — інтервал поширення вогню. Далі слідує число $k$ ( $1 \leq k \leq a \cdot b$ 1 \leq k \leq a \cdot b) — кількість осередків займання. Далі у $k$ рядках подано по два числа — координати клітин, де починається пожежа.

Вихідні дані

Виведіть мінімальний рівень небезпеки шляху з $(1, 1)$ до $(a, b)$ . Якщо такого шляху не існує, виведіть "-1".

Приклади

Приклад

Приклад

-1

Приклад 1

Примітка

У першому прикладі павук може рухатися шляхом $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (3, 3) \to (4, 3)$ (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (4, 3). Небезпечною є спочатку клітинка $(1, 1)$ , бо поряд з нею горить $(2, 1)$ . У клітині $(1, 2)$ пожежа ще не поширилася, тому ця клітинка безпечна. У $(1, 3)$ загоряються додаткові клітини — $(1, 1)$ , $(2, 2)$ , $(3, 1)$ , але жодна з них не межує з $(1, 3)$ , тому вона безпечна. Далі у $(2, 3)$ , де поруч $(2, 2)$ — горить, тож ця клітина небезпечна. У $(3, 3)$ поруч загоряється $(3, 2)$ — клітина також небезпечна. Нарешті, $(4, 3)$ — безпечна, бо нових осередків пожежі поруч немає. Небезпека шляху дорівнює $3$ ( $(1, 1)$ , $(2, 3)$ та $(3, 3)$ ). Жоден інший шлях не дозволяє уникнути пожежі.

У другому прикладі через три секунди загоряється $(4, 3)$ , і павук не встигає потрапити до неї.