Alpinistul

     Un alpinist ar vrea sa cucereasca un vârf cât mai înalt din Muntii Carpati. Din pacate îi este frica sa urce de pe o stânca pe alta alaturata, daca diferenta de altitudine depaseste 100 de metri. În schimb el coboara fara frica de pe o stânca pe alta alaturata, indiferent de diferenta de altitudine.

     Alpinistul are harta muntelui pe care vrea sa-l escaladeze. Harta este codificata sub forma unui caroiaj în care în patratele sunt notate altitudinile punctelor (înaltimile stâncilor) de pe harta, date în metri fata de ni­ve­lul marii. Alpinistul poate porni din orice patratel de pe harta cu altitudine 0 (aflat la nivelul marii) si poate efectua un pas doar într-o portiune de teren corespunzatoare unui patratel de pe harta, învecinat pe verticala sau pe orizontala cu patratelul în care se afla, cu conditia sa nu îi fie frica.

Cerinta

     Alpinistul apeleaza la ajutorul vostru pentru a afla traseul de lungime minima pe care trebuie sa-l urmeze pentru a escalada un vârf cât mai înalt.

Date de intrare

Fisier de intrare: ALPINIST.IN

Linia 1: M N

·         doua numere naturale nenule, separate printr-un spatiu, reprezentând dimensiunile caroiajului cores­pun­za­tor hartii;

Liniile 2..M + 1: v1 v2 ... vN

·         pe aceste M linii sunt scrise câte N numere naturale, separate prin câte un spatiu, re­pre­zen­tând valorile asociate caroiajului care codifica harta (linie dupa linie).

Date de iesire

Fisier de iesire: ALPINIST.OUT

Linia 1: I

·         numar natural ce reprezinta înaltimea maxima la care poate ajunge alpinistul;

Linia 2: XP YP XD YD

·         patru numere naturale nenule, separate prin câte un spatiu, reprezentând coordonatele patratelului din care pleaca alpinistul si coordonatele patratelului având înaltimea maxima în care poate ajunge; prin coordonatele patratelului se înteleg numarul liniei si cel al coloanei pe care se afla patratelul în caroiaj;

Linia 3: L

·         numar natural reprezentând lungimea drumului; lungimea unui drum se defineste ca fiind egal cu nu­ma­­rul patratelelor strabatute de alpinist;

Linia 4: D1 D2 ... DL

·         L caractere, separate prin câte un spatiu, reprezentând directia în care se misca alpinistul la fiecare pas i, i = 1, 2, ..., L; caracterele pot fi: 'N'– corespunzator unei miscari în sus, 'S'– corespunzator unei miscari în jos, 'W'– corespunzator unei miscari la stânga, 'E'– corespunzator unei miscari la dreapta.

Restrictii

·         2 <= M,N <= 100

·         0 <= vi <= 1000 i =1,2, ...,N (pe fiecare din cele M  linii)

·         daca sunt mai multe drumuri de lungime minima, în fisier se va scrie unul singur.

Exemplu

ALPINIST.IN                  

3 5
0 101 2 14 100
50 149 149 250 200
0 100 10 400 10

ALPINIST.OUT (un continut posibil)

250
1 1 2 4
8
S E E N E E S W

Timp maxim de executare/test: 1 secunda