alpinistul

Un alpinist ar vrea să cucerească un vârf cât mai înalt din Munţii Carpaţi. Din păcate îi este frică să urce de pe o stâncă pe alta alăturată, dacă diferenţa de altitudine depăşeşte $100$ de metri. În schimb el coboară fără frică de pe o stâncă pe alta alăturată, indiferent de diferenţa de altitudine.

Alpinistul are harta muntelui pe care vrea să-l escaladeze. Harta este codificată sub forma unui caroiaj în care în pătrăţele sunt notate altitudinile punctelor (înălţimile stâncilor) de pe hartă, date în metri faţă de nivelul mării. Alpinistul poate porni din orice pătrăţel de pe hartă cu altitudine $0$ (aflat la nivelul mării) şi poate efectua un pas doar într-o porţiune de teren corespunzătoare unui pătrăţel de pe hartă, învecinat pe verticală sau pe orizontală cu pătrăţelul în care se află, cu condiţia să nu îi fie frică.

Cerinţă

Alpinistul apelează la ajutorul vostru pentru a afla traseul de lungime minimă pe care trebuie să-l urmeze pentru a escalada un vârf cât mai înalt.

Date de intrare

Pe prima linie a fișierului de intrare alpinist.in se găsesc două numere întregi, $M$ și $N$, reprezentând dimensiunile caroiajului corespunzător hărţii. Pe urmatoarele $M$ linii sunt scrise câte $N$ numere naturale, separate prin câte un spaţiu, reprezentând valorile asociate caroiajului care codifică harta (linie după linie).

Date de ieșire

Pe prima linie a fișierului de ieşire alpinist.out se află $I$, număr natural ce reprezintă înălţimea maximă la care poate ajunge alpinistul; Pe linia $2$ se află $X_P$, $Y_P$, $X_D$, $Y_D$, patru numere naturale nenule, separate prin câte un spaţiu, reprezentând coordonatele pătrăţelului din care pleacă alpinistul şi coordonatele pătrăţelului având înălţimea maximă în care poate ajunge; prin coordonatele pătrăţelului se înţeleg numărul liniei şi cel al coloanei pe care se află pătrăţelul în caroiaj; Pe următoarea linie se află $L$, număr natural reprezentând lungimea drumului; lungimea unui drum se defineşte ca fiind egal cu numărul pătrăţelelor străbătute de alpinist; Pe următoarea linie se află $L$ caractere, separate prin câte un spaţiu, reprezentând direcţia în care se mişcă alpinistul la fiecare pas $i$; caracterele pot fi: N – corespunzător unei mişcări în sus, S – corespunzător unei mişcări în jos, W – corespunzător unei mişcări la stânga, E – corespunzător unei mişcări la dreapta.

Restricții și precizări

• $2 \leq M,N \leq 100$
• $0 \leq v_i \leq 1 \ 000$
• dacă sunt mai multe drumuri de lungime minimă, în fişier 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

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