**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)**.
Dar pentru ca jocul a evoluat destul de mult de la prima aparitie din 1995, si pentru ca suntem in anul 2015, si pentru ca am reusit sa scapam cu bine de anul 2013, exista un coeficient de energie, si anume: **avem o matrice patratica $E$ de dimensiune $N$ cu semnificatia $E[i][j]$ este energia consumata pentru a sari de pe un munte care se afla pe linia $i$ pe un munte care se afla pe linia $j$**. Bineinteles, Rayman vrea sa aibe cat mai multa energie pentru obstacole asa ca voi trebuie sa-i alegeti **un drum care sa consume si cat mai putina energie. Rayman poate sa inceapa de oriunde**.
Dar pentru ca jocul a evoluat destul de mult de la prima aparitie din $1995$, si pentru ca suntem in anul $2015$, si pentru ca am reusit sa scapam cu bine de anul 2013, exista un coeficient de energie, si anume: **avem o matrice patratica $E$ de dimensiune $N$ cu semnificatia $E[i][j]$ este energia consumata pentru a sari de pe un munte care se afla pe linia $i$ pe un munte care se afla pe linia $j$**. Bineinteles, Rayman vrea sa aibe cat mai multa energie pentru obstacole asa ca voi trebuie sa-i alegeti **un drum care sa consume si cat mai putina energie. Rayman poate sa inceapa de oriunde**.
Rayman o sa va rasplateasca cu $100$ de puncte daca il ajutati sa treaca de toate planşele.
h2. Date de intrare
