Speedrun

Andrei a primit de la Moș Crăciun o consolă nouă.

Pentru că știe că îi plac jocurile de tip puzzle, tatăl său i-a făcut cadou jocul Labyrinth. Jocul are două nivele ce pot fi descrise astfel:

• Nivelul 1: Personajul se află într-un labirint cu $N$ linii și $M$ coloane și are misiunea de a ajunge dintr-o celulă specificată $(L_1, C_1)$ într-o altă celulă $(L_2, C_2)$ fără să treacă prin celulele în care se află monștri. La fiecare pas, personajul se poate deplasa doar în patru direcții: sus, jos, stânga, dreapta.
• Nivelul 2: Misiunea personajului se păstrează și la acest nivel, însă apare o modificare. Astfel, în unele celule, care nu sunt ocupate de monștri, se găsește câte o cheie. La acest nivel, pentru a-și putea îndeplini misiunea de a se deplasa de la $(L_1, C_1)$ la $(L_2, C_2)$, personajul trebuie să treacă prin cel puțin o celulă ce conține o cheie.

Cerință

Cunoscând nivelul pe care îl joacă, determinați timpul minim în care Andrei poate termina misiunea știind că trecerea dintr-o celulă în alta durează o secundă.

Date de intrare

Pe prima linie a fișierului de intrare speedrun.in se vor afla patru numere naturale, date în ordine:

• $C$ - nivelul pe care urmează să îl joace Andrei;
• $N$, $M$ - dimensiunile labirintului, respectiv numărul de linii și coloane;
• $P$ - numărul de celule în care se găsesc chei.

Pe următoarea linie, vom găsi patru numere naturale $L_1$, $C_1$, $L_2$, $C_2$ cu semnificația din enunț.

Pe următoarele $N$ linii ale fișierului, se vor găsi câte $M$ valori de $0$ sau $1$ separate prin câte un spațiu cu semnificația următoare:

• $0$ - celula este liberă;
• $1$ - în celulă se găsește un monstru.

Pe următoarele $P$ linii, se va găsi câte o pereche de valori $(X, Y)$ reprezentând linia și coloana unei celule în care se găsește o cheie.

Date de ieșire

Pe prima linie a fișierului de ieșire speedrun.out se va găsi, indiferent de nivelul jucat, un singur număr natural, reprezentând numărul minim de secunde pentru a finaliza misiunea.

Restricții și precizări

• $1 \le N, M \le 1\ 000$
• $0 \le$ numărul de monștri $\le N \times M$
• $0 \le P \le N \times M$
• Pentru cerința 1, se garantează $P = 0$, și pentru cerința 2 vom avea $P \ge 1$.
• Va exista întotdeauna cel puțin o soluție.
• Se garantează $(L_1, C_1) \neq (L_2, C_2)$.
• Cheile se vor afla mereu pe celule care nu conțin monștri.
• Se oferă $10$ puncte din oficiu.

Exemplul 1

speedrun.in

1 6 6 0
1 1 5 6
0 0 1 1 1 1
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 1 0 0
1 1 0 0 0 0
1 1 1 0 1 1

speedrun.out

9

Explicație

Un posibil traseu pentru personaj ce conduce la soluție va trece prin celulele următoare: $(L_1, C_1) \Leftrightarrow (1, 1)$, $(1, 2)$, $(2, 2)$, $(3, 2)$, $(4, 2)$, $(4, 3)$, $(5, 3)$, $(5, 4)$, $(5, 5)$, $(5,6) \Leftrightarrow (L_2, C_2)$.

Exemplul 2

speedrun.in

2 6 6 1
1 1 5 6
0 0 1 1 1 1
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 1 0 0
1 1 0 0 0 0
1 1 1 0 1 1
4 6 

speedrun.out

11

Explicație

Un posibil traseu pentru personaj ce conduce la soluție va trece prin celulele următoare: $(L_1, C_1) \Leftrightarrow (1, 1)$, $(1, 2)$, $(2, 2)$, $(3, 2)$, $(3,3)$, $(3,4)$, $(2,4)$, $(2,5)$, $(2,6)$, $(3,6)$, $(4,6)$, $(5,6) \Leftrightarrow (L_2, C_2)$.