muzeu

Time limit: 0.1s Memory limit: 16MB Input: muzeu.in Output: muzeu.out

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 MM linii si NN 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,ji, j) deplasarea spre nord presupune trecerea în poziţia (i1,ji-1, j), spre est în (i,j+1i, j+1), spre sud în (i+1,ji+1, j) şi spre vest în (i,j1i, j-1).

Acest muzeu are câteva reguli speciale. Fiecare cameră este marcată cu un număr între 00 şi 1010 inclusiv. Mai multe camere pot fi marcate cu acelaşi număr. Camerele marcate cu numărul 00 pot fi vizitate gratuit. Într-o cameră marcată cu numărul ii se poate intra gratuit, dar nu se poate ieşi din ea decât dacă arătaţi supraveghetorului un bilet cu numărul ii. Din fericire, orice cameră cu numărul ii oferă spre vânzare un bilet cu numărul ii; 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 ii 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,11, 1) a matricei) şi doriţi să ajungeţi la ieşirea situată în colţul de Sud-Est (poziţia (M,NM, N) a matricei). O dată ajuns acolo primiţi un bilet gratuit care vă permite să vizitaţi tot muzeul. Poziţiile (1,11, 1) şi (M,NM, N) sunt marcate cu numărul 00.

Cerinţă

Cunoscându-se structura muzeului, determinaţi o strategie de parcurgere a camerelor, astfel încât să ajungeţi în camera (M,NM, 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 MM şi NN, separate printr-un spaţiu, numărul de linii, respectiv de coloane, al matricei care reprezintă muzeul. Următoarele MM linii conţin structura muzeului; fiecare conţine NN numere întregi între 00 şi 1010 inclusiv, separate prin spaţii. Linia M+2M+2 conţine 1010 numere întregi între 00 şi 10 00010 \ 000 inclusiv, reprezentând costurile biletelor 11, 22, 33, \dots, 1010 î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,11, 1) în (M,NM, N);
  • pe a doua linie numărul minim de mutări LL efectuate dintr-o cameră într-o cameră vecină, pentru a ajunge din (1,11, 1) în (M,NM, N);
  • pe a treia linie LL caractere din multimea NN, EE, SS, VV reprezentând deplasări spre Nord, Est, Sud sau Vest .

Restricții și precizări

  • 2N,M502 \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

Log in or sign up to be able to send submissions!