Евакуація

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

Павутина являє собою прямокутну сітку (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), а павук ніяк не встигне добратись до неї за три секунди.