Pracsiu Dan (dnprx) Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare.
Castelul tău are forma unui caroiaj cu M linii şi N coloane. Cele M x N celule ale castelului sunt numerotate de la 1 la M x N în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta. În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula i conţine cheia cu numărul i. Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maximum patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale. Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte.
Cerința
Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele M x N camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.
Date de intrare
Fișierul de intrare castel.in conţine pe prima linie trei numere naturale M N K separate prin câte un spaţiu reprezentând dimensiunile castelului, respectiv numărul camerei în care se află iniţial prinţesa. Urmează descrierea castelului. Pe fiecare dintre următoarele M linii se află câte N numere naturale cuprinse între 1 şi M x N reprezentând cheile necesare deschiderii fiecăreia dintre camere.
Date de ieșire
Fișierul de ieșire castel.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul de camere accesibile prinţesei.
Restricții și precizări
1 ≤ M, N ≤ 1501 ≤ K ≤ M * N- Odată ce prinţesa a păşit într-o cameră, respectiva cameră va rămâne pentru totdeauna deschisă.
Exemplu:
castel.in
4 3 1 1 1 4 1 6 2 6 9 8 12 10 11
castel.out
7
Explicație
Prinţesa porneşte din camera 1. Aici foloseşe cheia 1 şi intră în camera 4. Se întoarce în camera 1 şi descuie camera 2. Foloseşte cheia luată din camera 4 şi descuie camera 3. În acest moment ea deţine cheile 1, 2, 3 şi 4. Foloseşte cheia 2 şi intră în camera 6, apoi foloseşte cheia 6 şi intră în camera 5, apoi în camera 4, de unde, folosind cheia luată din camera 6 intră în camera 7. La final prinţesa are cheile 1, 2, 3, 4, 5, 6, 7 şi nu mai poate deschide nici o altă cameră.