Copaci

Pentru a se relaxa, Dan se plimbă printr-o pădure virtuală formată din $N \times N$ copaci, așezați sub forma unei matrici pătratice cu $N$ linii și $N$ coloane. Pe fiecare copac este scrisă o cifră din baza $10$.
Plimbarea lui Dan începe de la un copac aflat într-o poziție de coordonate necunoscute și constă dintr-o succesiune de pași. La fiecare pas, Dan se va deplasa la unul dintre copacii vecini. Doi copaci sunt vecini dacă se află pe aceeași linie pe coloane consecutive, sau se află pe aceeași coloană, pe linii consecutive. Pe parcursul plimbării, Dan memorează într-un șir $S$ cifrele scrise pe copacii aflați în pozițiile prin care a trecut. Fiind însă foarte obosit, este posibil ca la un moment dat să fi memorat greșit cifrele în șirul $S$.

Cerință

Dată fiind matricea care reprezintă pădurea virtuală, precum și șirul $S$ în care au fost memorate cifrele de pe copacii situați în pozițiile vizitate de Dan pe parcursul plimbării, să se determine numărul maxim de poziții vizitate pe parcursul plimbării, până la prima cifră memorată greșit în șirul $S$.

Date de intrare

Fişierul de intrare copaci.in conţine pe prima linie numărul natural $N$. Pe următoarele $N$ linii se află câte $N$ cifre, reprezentând cifrele scrise pe copacii din pădurea virtuală, în ordinea liniilor, iar pentru copacii de pe aceeași linie, în ordinea coloanelor. Pe ultima linie se află cifrele memorate în șirul $S$. În fișierul de intrare nu sunt spații.

Date de ieșire

Fișierul de ieșire copaci.out va conține o singură linie pe care va fi scris un singur număr natural, reprezențând răspunsul la cerința dată.

Restricții și precizări

• $1 \leq N \leq 100$
• $1 \leq |S| \leq 10^5$

Exemplul 1

copaci.in

3
769
617
502
97205562

copaci.out

5

Explicație

Numărul maxim de poziții parcurse până la prima cifră memorată greșit în $S$ este $5$. O plimbare posibilă este:
$\textcolor{white}{7 \ 6} \ \textcolor{blue}{9}$
$\textcolor{white}{6 \ 1} \ \textcolor{blue}{7}$
$\textcolor{blue}{5 \ 0 \ 2}$

Exemplul 2

copaci.in

3
125
452
803
32541

copaci.out

5

Explicație

Șirul $S$ este corect în întregime. O plimbare posibilă este:
$\textcolor{blue}{1} \ \textcolor{white}{2 \ 5}$
$\textcolor{blue}{4 \ 5 \ 2}$
$\textcolor{white}{8 \ 0} \ \textcolor{blue}{3}$

Exemplul 3

copaci.in

5
36231
92928
08044
51868
43301
6281864292913

copaci.out

11

Explicație

Numărul maxim de poziții parcurse până la prima cifră memorată greșit în $S$ este $11$. O plimbare posibilă este:
$\textcolor{white}{3} \ \textcolor{blue}{6} \ \textcolor{white}{2 \ 3 \ 1}$
$\textcolor{blue}{9} \ \textcolor{purple}{2} \ \textcolor{blue}{9 \ 2} \ \textcolor{white}{8}$
$\textcolor{white}{0} \ \textcolor{blue}{8} \ \textcolor{white}{0} \ \textcolor{blue}{4} \ \textcolor{white}{4}$
$\textcolor{white}{5} \ \textcolor{blue}{1 \ 8 \ 6} \ \textcolor{white}{8}$
$\textcolor{white}{4 \ 3 \ 3 \ 0 \ 1}$
Observați că pe parcursul plimbării Dan poate trece de mai multe ori prin aceeași poziție.

Exemplul 4

copaci.in

2
30
47
121

copaci.out

0

Explicație

Numărul maxim de poziții parcurse până la prima cifră memorată greșit în $S$ este $0$, pentru că nu există niciun copac pe care să fie scrisă cifra $1$.