== include(page="template/taskheader" task_id="rayman") ==
!>problema/rayman?img.png!
Cred că toată lumea s-a jucat Rayman şi îi cunoaşte protagonistul.
Au apărut planşe noi în renumitul joc şi voi aveţi datoria de a-i spune lui Rayman pe unde să meargă. O planşă este alcătuită din mai mulţi munţi de diferite înălţimi pe vârful cărora se află câte un obstacol cu un grad de risc anume. Mai exact, planşa arată ca o matrice cu $N$ linii şi $M$ coloane, iar fiecare căsuţă din matrice reprezintă un munte cu obstacolul sau. Deoarece Mister Dark, Admiral Rezorbeard, Andre şi The Magician şi-au unit forţele şi au inventat o poţiune care să-i alunge lui Rayman puterea de a zbura, **acesta poate să sară de pe un munte numai pe altul cu înălţime mai mică sau egală**. Ştim cu toţii că lui Rayman îi place cel mai mult aventura, **aşa că acesta doreşte să treacă prin cât mai multe obstacole**, dar, mai ştim că Rayman este un om superstiţios, deci el nu vrea să se întoarcă din drum (acesta crede că Mister Unlucky o să dea năvală peste el şi o să-l omoare).
Au apărut planşe noi în renumitul joc şi voi aveţi datoria de a-i spune lui Rayman pe unde să meargă. O planşă este alcătuită din mai mulţi munţi de diferite înălţimi pe vârful cărora se află câte un obstacol cu un grad de risc anume. Mai exact, planşa arată ca o matrice cu $N$ linii şi $M$ coloane, iar fiecare căsuţă din matrice reprezintă un munte cu obstacolul sau. Deoarece Mister Dark, Admiral Rezorbeard, Andre şi The Magician şi-au unit forţele şi au inventat o poţiune care să-i alunge lui Rayman puterea de a zbura, **acesta poate să sară de pe un munte numai pe altul cu înălţime mai mică sau egală**. Ştim cu toţii că lui Rayman îi place cel mai mult aventura, **aşa că acesta doreşte să treacă prin cât mai multe obstacole**, dar, mai ştim că Rayman este un om superstiţios, deci el nu vrea să se întoarcă din drum (aceste crede că Mister Unlucky o să dea năvală peste el şi o să-l omoare).
Mai exact, **dacă la un moment dat el se află pe un munte pe linia $x$ şi coloana $y$ atunci în viitor el poate să ajungă pe un munte de pe linia $x$ şi coloana $y1$ doar dacă $y < y1$** (cu alte cuvinte, dacă înşiruirea de mutări este <tex> (x_1, y_1), (x_2, y_2), .., (x_k, y_k), (a, b_1), (x_{k+1}, y_{k+1}), ..., (x_s, y_s), (a, b_2), (x_{s+1}, y_{s+1}), ..., (x_q, y_q),</tex> atunci nu este permis ca <tex>b_1 > b_2</tex>). Totuşi, noi mai ştim că la cât de neînfricat este Rayman, el nu doreşte să îşi asume foarte multe riscuri, prin urmare voi trebuie să îi alegeţi un drum care **să treacă prin cât mai multe obsacole, dar cu gradul total de risc minim (în caz de egalitate după lungime)**. Pentru că lui nu îi place să piardă timpul alegând din mai multe trasee şi doreşte să plece la drum cât mai repede posibil, **acesta va garantează că există o singură mulţime de obstacole cu cardinal maxim care poate fi parcursă în condiţiile de mai sus, care să aibă un grad total de risc minim (drumul propriu-zis nefiind neapărat unic)**.
Dar pentru că jocul a evoluat destul de mult de la prima apariţie din $1995$, şi pentru că suntem în anul $2015$, şi pentru că am reuşit să scăpăm cu bine de anul $2013$, există un coeficient de energie, şi anume: fie matrice pătratică $E$ de dimensiune $N$ cu semnificaţia **$E[i][j]$ este energia consumată pentru a sări de pe un munte care se află pe linia $i$ pe un munte care se află pe linia $j$. Dar toată lumea ştie că Rayman poate să sară foarte mult şi energia consumată pentru o săritură nu depinde de lungimea săriturii cât depinde de săritura propriu-zisă, aşa că el consumă mai multă energie dacă sare printr-o piatră intermediară, cu alte cuvinte se garanteaza că $E[i][j] ≤ E[i][k] + E[k][j]$, oricare ar fi $k$**. Bineînţeles, Rayman vrea să aibe cât mai multă energie pentru obstacole, aşa că voi trebuie să-i alegeţi **un drum care să consume şi cât mai puţină energie, în caz că există mai multe cu acelaşi cardinal şi grad total de risc. Rayman poate să înceapă de oriunde**.
Dar pentru că jocul a evoluat destul de mult de la prima apariţie din $1995$, şi pentru că suntem în anul $2015$, şi pentru că am reuşit să scăpăm cu bine de anul 2013, există un coeficient de energie, şi anume: fie matrice pătrăţica $E$ de dimensiune $N$ cu semnificaţia **$E[i][j]$ este energia consumată pentru a sări de pe un munte care se află pe linia $i$ pe un munte care se află pe linia $j$**. Bineînţeles, Rayman vrea să aibe cât mai multă energie pentru obstacole aşa că voi trebuie să-i alegeţi **un drum care să consume şi cât mai puţină energie, în caz că există mai multe cu acelaşi cardinal şi grad total de risc. Rayman poate să înceapă de oriunde**.
Rayman o să va răsplătească cu $100$ de puncte dacă îl ajutaţi să treacă de toate planşele.
h2. Date de intrare
Pe prima linie a fişierului $rayman.in$ se află două numere natural $N$ şi $M$ cu semnificaţiile de mai sus. Pe următoarele $N$ linii se află câte $M$ numere care reprezintă înălţimile munţilor. Fişierul de intrare mai conţine încă $N$ linii a câte $M$ numere care reprezintă gradul de risc al obstacolelor. Pe următoarele $N$ linii se află câte $N$ numere care reprezintă matricea $E$.
Pe prima linie a fişierului $rayman.în$ se află două numere natural $N$ şi $M$ cu semnificaţiile de mai sus. Pe următoarele $N$ linii se află câte $M$ numere care reprezintă înălţimile munţilor. Fişierul de intrare mai conţine încă $N$ linii a câte $M$ numere care reprezintă gradul de risc al obstacolelor. Pe următoarele $N$ linii se află câte $N$ numere care reprezintă matricea $E$.
h2. Date de ieşire
Traseul pe care îl urmează Rayman este: $(3, 3) -> (3, 4) -> (2, 2) -> (2, 3) -> (2, 4) -> (3, 5) -> (2, 6) -> (1, 1) -> (1, 2) -> (1, 5) -> (1, 6)$
== include(page="template/taskfooter" task_id="rayman") ==
== include(page="template/taskfooter" task_id="rayman") ==
