James Bomb are o nouă misiune de îndeplinit. El se află într-o clădire cu m etaje. Fiecare etaj poate fi privit ca un caroiaj având n x p celule.
     Într-un anumit loc din clădire se află o bombă care explodează după t minute. Agentul 008 poate să dezamorseze bomba în w minute, dar mai intai trebuie sa ajungă la ea.
     În fiecare minut James Bomb se poate deplasa cu o celulă pe orizontală (stânga/dreapta sau înainte/înapoi) și verticală (sus/jos) într-o celulă goală.
     Sarcina voastră este ca, pe baza hărții clădirii, a poziției lui James Bomb și a poziției bombei, să stabiliți dacă James Bomb are timp sau nu să dezamorseze bomba.
     În cazul în care James Bomb are timp să dezamorseze bomba, determinați timpul minim necesar în care el ajunge la bombă.
     În caz contrar, determinați timpul minim necesar în care James Bomb poate părăsi clădirea.

Fișierul de intrare JBOMB.IN conține pe prima linie trei numere m, n și p, separate între ele prin spațiu, care reprezintă dimensiunile clădirii. A doua linie conține două numere t și w, separate printr-un singur spațiu, care reprezintă timpul în care bomba explodează, respectiv timpul în care James Bomb poate să dezamorseze bomba.
    Cea de-a treia linie conține trei numere, separate între ele prin spații, care reprezintă coordonatele bombei.
    Cea de-a patra linie conține trei numere, separate între ele prin spații, care reprezintă coordonatele lui James Bomb.
    În continuare urmează harta celor m etaje. Fiecare etaj este descris de n linii.
    Pe fiecare dintre liniile corespunzatoare descrierii unui etaj se află p numere care nu sunt separate prin spații și care pot avea valorile 0 sau 1.
    Valoarea 0 indica faptul că celula respectiva este libera, iar valoarea 1 indică faptul că celula respectivă este ocupată (conține zid).

Fișierul de ieșire JBOMB.OUT trebuie să conțină o singura linie pe care se vor afla două numere separate între ele printr-un singur spațiu.

    Primul număr va avea valoarea 1 dacă James Bomb are timp să dezamorseze bomba, caz în care cel de-al doilea număr reprezintă timpul minim în care Agentul 008 poate ajunge la bombă și valoarea 0 dacă James Bomb nu are timp să dezamorseze bomba, caz în care cel de-al doilea număr reprezinta timpul minim în care Agentul 008 poate părăsi clădirea.

  • 3 ≤ m, n, p ≤ 20;
  • 1 ≤ w, t ≤ 100;
  • se garantează existența unei soluții;
  • celulele în care se află bomba și inițial James Bomb sunt goale;
  • poziția inițială a lui James Bomb este diferită de cea a bombei;
  • James Bomb poate părăsi clădirea dacă se află într-o celulă liberă de pe marginea clădirii și nu are timp să dezamorseze bomba.


  • JBOMB.IN
    3 3 3
    5 2
    3 3 2
    1 2 2
    011
    001
    111
    000
    100
    001
    111
    111
    101

    JBOMB.OUT
    1 3