Problem
Dans un tableau rectangulaire NxM (dans chaque cellule dont un certain nombre est écrit), au début le joueur est dans la cellule supérieure gauche.
En un coup, il est autorisé à se déplacer vers la cellule suivante soit vers la droite, soit vers le bas (il est interdit de se déplacer vers la gauche et vers le haut).
Lorsqu'il traverse une cellule, le joueur est facturé autant de c.u.
Il est nécessaire de trouver le montant minimum de c.u., en payant, que le joueur peut atteindre dans le coin inférieur droit.
Saisie :
- la première ligne contient deux nombres N et M - tailles de tableau (\(1<=N<=20 \), \(1<=M<=20\));
- alors il y a N lignes de M nombres dans chacune - tailles d'amendes en c.u. pour passer par les cellules correspondantes (chaque chiffre de 0 à 100).
Sortie : imprimez le montant minimum que vous pouvez dépenser pour obtenir dans le coin inférieur droit.
Exemples
| # |
Entrée |
Sortie |
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
8 |