muzeu

Sunteţi un participant la Olimpiada Naţională de Informatică. În programul olimpiadei intră şi câteva activităţi de divertisment. Una dintre ele este vizitarea unui muzeu. Acesta are o structură de matrice dreptunghiulară cu $M$ linii si $N$ coloane; din orice cameră se poate ajunge în camerele vecine pe direcţiile nord, est, sud şi vest (dacă aceste camere există). Pentru poziţia ($i, j$) deplasarea spre nord presupune trecerea în poziţia ($i-1, j$), spre est în ($i, j+1$), spre sud în ($i+1, j$) şi spre vest în ($i, j-1$).

Acest muzeu are câteva reguli speciale. Fiecare cameră este marcată cu un număr între $0$ şi $10$ inclusiv. Mai multe camere pot fi marcate cu acelaşi număr. Camerele marcate cu numărul $0$ pot fi vizitate gratuit. Într-o cameră marcată cu numărul $i$ se poate intra gratuit, dar nu se poate ieşi din ea decât dacă arătaţi supraveghetorului un bilet cu numărul $i$. Din fericire, orice cameră cu numărul $i$ oferă spre vânzare un bilet cu numărul $i$; o dată cumpărat acest bilet, el este valabil în toate camerele marcate cu numărul respectiv. Biletele pot avea preţuri diferite, dar un bilet cu numărul $i$ va avea acelaşi preţ în toate camerele în care este oferit spre vânzare.

Dumneavoastră intraţi în muzeu prin colţul de Nord-Vest (poziţia ($1, 1$) a matricei) şi doriţi să ajungeţi la ieşirea situată în colţul de Sud-Est (poziţia ($M, N$) a matricei). O dată ajuns acolo primiţi un bilet gratuit care vă permite să vizitaţi tot muzeul. Poziţiile ($1, 1$) şi ($M, N$) sunt marcate cu numărul $0$.

Cerinţă

Cunoscându-se structura muzeului, determinaţi o strategie de parcurgere a camerelor, astfel încât să ajungeţi în camera ($M, N$) plătind cât mai puţin. Dacă există mai multe variante, alegeţi una în care este parcurs un număr minim de camere (pentru a câştiga timp şi pentru a avea mai mult timp pentru vizitarea integrală a muzeului).

Date de intrare

Prima linie a fişierului de intrare muzeu.in conţine două numere întregi $M$ şi $N$, separate printr-un spaţiu, numărul de linii, respectiv de coloane, al matricei care reprezintă muzeul. Următoarele $M$ linii conţin structura muzeului; fiecare conţine $N$ numere întregi între $0$ şi $10$ inclusiv, separate prin spaţii. Linia $M+2$ conţine $10$ numere întregi între $0$ şi $10 \ 000$ inclusiv, reprezentând costurile biletelor $1$, $2$, $3$, $\dots$, $10$ în această ordine.

Date de ieșire

În fişierul muzeu.out veţi afişa:

• pe prima linie suma minimă necesară pentru a ajunge din ($1, 1$) în ($M, N$);
• pe a doua linie numărul minim de mutări $L$ efectuate dintr-o cameră într-o cameră vecină, pentru a ajunge din ($1, 1$) în ($M, N$);
• pe a treia linie $L$ caractere din multimea $N$, $E$, $S$, $V$ reprezentând deplasări spre Nord, Est, Sud sau Vest .

Restricții și precizări

• $2 \leq N, M \leq 50$;

Exemplu

muzeu.in

5 6 
0 0 0 0 0 2
0 1 1 1 4 3
0 1 0 0 0 0
0 1 5 1 0 0
0 0 0 1 0 0
1000 5 7 100 12 1000 1000 1000 1000 1000

muzeu.out

12
9
EEEEESSSS