smart

Într-un laborator de cercetări în domeniul geneticii, s-a obţinut o rasă de şoareci inteligenţi. Pentru a demonstra public acest lucru, cercetătorii au introdus $k$ şoareci în celula $X$ a unui labirint format din $n \cdot n$ celule pătratice. Unele celule sunt accesibile, iar altele nu.

Pe fiecare perete care desparte două celule accesibile, se află câte o gaură (de şoarece!) prin care poate să treacă un singur şoarece, iar trecerea durează o secundă. 

Şoarecii participă voluntar la acest experiment şi au înţeles imediat că trebuie să ajungă cu toţii în cel mai scurt timp posibil în celula $Y$.

Cerință

Determinaţi timpul minim necesar pentru ca toţi şoarecii să ajungă în celula $Y$.

Date de intrare

În fisierul smart.in, se află pe prima linie numerele naturale $n$ şi $k$, reprezentând dimensiunea labirintului, respectiv numărul de şoareci care au fost de acord să participe la experiment.
Pe fiecare dintre următoarele $n$ linii, se găsesc câte $n$ caractere care codifică labirintul. Caracterul 0 semnifică o celulă accesibilă iniţial neocupată, 1 o celulă inaccesibilă, X este celula accesibilă de plecare, iar Y este celula accesibilă de sosire. 

Date de ieșire

Fisierul smart.out va conţine o singură linie pe care se va scrie un număr $T$, reprezentând cel mai scurt timp posibil necesar pentru ca toţi şoarecii să ajungă în celula $Y$.

Restricții și precizări

• $1 \leq n \leq 50$
• $1 \leq k \leq 100$
• $2 \leq$ numărul de celule accesibile $\leq 300$
• Timpul de deplasare a şoarecilor în interiorul unei celule este neglijabil.
• Într-o celulă accesibilă se pot afla la un moment dat oricâţi şoareci.

Exemplul 1

smart.in

3 4
X00
010
0Y0

smart.out

5

Explicație

Exemplul este cel din figură.

Să notăm cei patru şoareci cu $s_1$, $s_2$, $s_3$ şi $s_4$.
După prima secundă, $s_1$ a trecut în celula $B_1$ şi $s_2$ în celula $A_2$.
După secunda a doua, $s_1$ a ajuns în $C_1$, $s_2$ în $A_3$, iar $s_3$ a intrat în $B_1$.
După secunda a treia, $s_1$ a ajuns în $Y$, $s_2$ în $B_3$, $s_3$ în $C_1$, iar s4 în $B_1$.
După $4$ secunde, $s_2$ ajunge în $C_3$, $s_3$ ajunge în $Y$, $s_4$ in $C_1$.
După secunda $5$, $s_2$ şi $s_4$ au ajuns în celula $Y$.