== include(page="template/taskheader" task_id="rayman") ==
Cred ca toata lumea s-a jucat Rayman si ii cunoaste protagonistul.

Au aparut planşe noi in renumitul joc si voi aveti datoria de a-i spune lui Rayman pe unde sa mearga. O plansa este alcatuita din mai multi munti de diferite inaltimi pe varful carora se afla cate un obstacol cu un grad de risc anume. Mai exact, planşa arata ca o matrice cu $N$ linii si $M$ coloane, iar fiecare casuta din matrice reprezinta un munte cu obstacolul sau. Deoarece Mister Dark, Admiral Rezorbeard, Andre si The Magician si-au unit fortele si au inventat o potiune care sa-i alunge lui Rayman puterea de a zbura, **acesta poate sa sara de pe un munte numai pe altul cu inaltime mai mica sau egala**. Stim cu totii ca lui Rayman ii place cel mai mult aventura, **asa ca acesta doreste sa treaca prin cat mai multe obstacole**, dar mai stim ca Rayman este un om superstitios, **asa ca el nu vrea sa se intoarca din drum** (aceste crede ca Mister Unlucky o sa dea navala peste el si o sa-l omoare).

Au aparut planşe noi in renumitul joc si voi aveti datoria de a-i spune lui Rayman pe unde sa mearga. O plansa este alcatuita din mai multi munti de diferite inaltimi pe varful carora se afla cate un obstacol cu un grad de risc anume. Mai exact, planşa arata ca o matrice cu $N$ linii si $M$ coloane, iar fiecare casuta din matrice reprezinta un munte cu obstacolul sau. Deoarece Mister Dark, Admiral Rezorbeard, Andre si The Magician si-au unit fortele si au inventat o potiune care sa-i alunge lui Rayman puterea de a zbura, **acesta poate sa sara de pe un munte numai pe altul cu inaltime mai mica sau egala**. Stim cu totii ca lui Rayman ii place cel mai mult aventura, **asa ca acesta doreste sa treaca prin cat mai multe obstacole**, dar mai stim ca Rayman este un om superstitios, asa ca el nu vrea sa se intoarca din drum (aceste crede ca Mister Unlucky o sa dea navala peste el si o sa-l omoare).

**Mai exact, daca la un moment dat el se afla pe un munte pe linia $x$ si coloana $y$ atunci in viitor el poate sa ajunga pe un munte pe linia $x$ si coloana $y1$ doar daca $y < y1$** (cu alte cuvinte, daca insiruirea de mutari 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>). Totusi noi mai stim ca la cat de neinfricat este Rayman, el nu doreste sa isi asume foarte multe riscuri, **asa ca voi trebuie sa ii alegeti un drum care sa treaca prin cat mai multe obsacole, dar cu gradul total de risc minim**. Pentru ca lui nu ii place sa piarda timpul alegand din mai multe trasee si doreste sa plece la drum cat mai repede posibil, **acesta va garanteaza ca exista o singura multime de obstacole cu cardinal maxim care poate fi parcursa in conditiile de mai sus, care sa aiba un grad total de risc minim (drumul propriu-zis nefiind neaparat unic)**.