Se citesc doua numere naturale n si m, apoi o matrice de costuri cu n linii si m coloane. Determinati, folosind Programarea Dinamica, costul minim al unui drum de la celula (1,1) la celula (n,m), stiind ca la fiecare pas ne putem deplasa fie la dreapta, fie in jos, iar costul unui drum este suma costurilor tuturor celulelor vizitate.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza n linii, fiecare cu m valori reprezentand costurile celulelor.
- Date de iesire
- Se afiseaza un singur numar: costul minim al unui drum de la (1,1) la (n,m).
- Restrictii
- 1 <= n, m <= 1000, 0 <= cost <= 1000
Exemple
Exemplul 1
Intrare
2 2 1 2 3 4
Iesire
7
Exemplul 2
Intrare
3 3 1 3 1 1 5 1 4 2 1
Iesire
7