Problem 1185: scufita

Majoritatea participanţilor la ONI2003 au auzit, în copilărie, povestea Scufiţei Roşii. Pentru cei care o ştiu, urmează partea a doua; pentru cei care nu o ştiu, nu vă faceţi griji, cunoaşterea ei nu este necesară pentru a rezolva această problemă. Povestea nu spune ce s-a întâmplat pe drumul pe care Scufiţa Roşie s-a întors de la bunicuţă. Veţi afla amănunte în continuare.

Pe drum, ea s-a întâlnit cu Lupul (fratele lupului care a părăsit povestea în prima parte). Acesta dorea să o mănânce, dar a decis să-i acorde o şansă de scăpare, provocând-o la un concurs de cules ciupercuţe.

Scufiţa Roşie se află în poziţia ( $1, 1$ ) a unei matrici cu $N$ linii şi $N$ coloane, în fiecare poziţie a matricei fiind amplasate ciupercuţe. Lupul se află în poziţia ( $1, 1$ ) a unei alte matrici similare. Pe parcursul unui minut, atât Scufiţa, cât şi Lupul se deplasează într-una din poziţiile vecine (pe linie sau pe coloană) şi culeg ciupercuţele din poziţia respectivă. Dacă Scufiţa Roşie ajunge într-o poziţie în care nu sunt ciupercuţe, va pierde jocul. Dacă la sfârşitul unui minut ea are mai puţine ciupercuţe decât Lupul, ea va pierde jocul de asemenea. Jocul începe după ce amândoi participanţii au cules ciupercuţele din poziţiile lor iniţiale (nu contează cine are mai multe la începutul jocului, ci doar după un număr întreg strict pozitiv de minute de la început). Dacă Scufiţa Roşie pierde jocul, Lupul o va mânca.

Înainte de începerea jocului, Scufiţa Roşie l-a sunat pe Vânător, care i-a promis că va veni într-un sfert de ora ( $15$ minute) pentru a o salva. Deci Scufiţa Roşie va fi liberă să plece dacă nu va pierde jocul după $15$ minute.

Din acest moment, scopul ei este nu numai să rămână în viaţă, ci şi să culeagă cât mai multe ciupercuţe, pentru a le duce acasă (după ce va veni, vânătorul nu o va mai lăsa să culeagă). Lupul, cunoscut pentru lăcomia sa proverbială, va alege la fiecare minut mutarea în câmpul vecin cu cele mai multe ciupercuţe (matricea sa este dată astfel încât să nu existe mai multe posibilităţi de alegere la un moment dat). Povestea spune că Scufiţa Roşie a plecat acasă cu coşuleţul plin de ciupercuţe, folosind indicaţiile date de un program scris de un concurent la ONI 2003 (nu vom da detalii suplimentare despre alte aspecte, cum ar fi călătoria în timp, pentru a nu complica inutil enunţul problemei). Să fi fost acest program scris de dumneavoastră? Vom vedea...

Cerinţă

Scrieţi un program care să o ajute pe Scufiţa Roşie să rămână în joc şi să culeagă cât mai multe ciupercuţe la sfârşitul celor $15$ minute!

Date de intrare

Fişierul scufita.in are următoarea structură:

Pe prima linie se va citi $N$ - dimensiunea celor două matrice
Pe următoarele $n$ linii se vor afla câte $n$ valori, reprezentând matricea $a$ , cea din care culege Scufița Roșie.
Pe următoarele $n$ linii se vor afla câte $n$ valori, reprezentând matricea $b$ , cea din care culege Lupul.

Date de ieșire

Fişierul scufita.out are următoarea structură:

Pe prima linie se va afisa $NR$ - numărul total de ciupercuţe culese
Pe cea de-a doua linie se vor afisa $d_1$ , $d_2$ , $\dots$ , $d_{15}$ - direcţiile pe care s-a deplasat Scufiţa Roşie, separate prin câte un spaţiu (direcţiile pot fi $N$ , $E$ , $S$ , $V$ indicând deplasări spre Nord, Est, Sud, Vest; poziţia ( $1, 1$ ) este situată în colţul de Nord-Vest al matricei)

Restricții și precizări

$4 \leq N \leq 10$ ;
valorile din ambele matrici sunt numere naturale mai mici decât $256$ ;
nici Scufiţa Roşie şi nici Lupul nu vor părăsi matricele corespunzătoare;
după ce unul din jucători culege ciupercuţele dintr-o poziţie, în poziţia respectivă rămân $0$ ciupercuţe;
pe testele date, Scufiţa Roşie va avea întotdeauna posibilitatea de a rezista $15$ minute.
se acceptă orice soluție corectă.

Exemplu

scufita.in

4			
2 2 3 4			
5 6 7 8
9 10 11 12
13 14 15 16
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

scufita.out

137
SSSEEENVVNEENVV

Explicație

Scufiţa Roşie a efectuat aceleaşi mutări cu cele efectuate de Lup şi a avut tot timpul o ciupercuţă în plus. În final ea a cules toate ciupercuţele din matrice.

scufita