Se consideră o matrice dreptunghiulară cu linii şi coloane, cu valori naturale. Traversăm matricea pornind de la colţul stânga-sus la colţul dreapta-jos. O traversare constă din mai multe deplasări. La fiecare deplasare se execută un salt pe orizontală şi un pas pe verticală. Un salt înseamnă că putem trece de la o celulă la oricare alta aflată pe aceeaşi linie, iar un pas înseamnă că putem trece de la o celulă la celula aflată imediat sub ea. Excepţie face ultima deplasare (cea în care ne aflăm pe ultima linie), când vom face doar un salt pentru a ajunge în colţul dreapta-jos, dar nu vom mai face şi pasul corespunzător. Astfel traversarea va consta din vizitarea a celule.
Cerinţă
Scrieţi un program care să determine suma minimă care se poate obţine pentru o astfel de traversare.
Date de intrare
Fişierul de intrare lacusta.in conţine pe prima linie două numere naturale separate printr-un spaţiu , reprezentând numărul de linii şi respectiv numărul de coloane ale matricei. Pe următoarele linii este descrisă matricea, câte numere pe fiecare linie, separate prin câte un spaţiu.
Date de ieșire
Fişierul de ieşire lacusta.out va conţine o singură linie pe care va fi scrisă suma minimă găsită.
Restricții și precizări
- Valorile elementelor matricei sunt numere întregi din intervalul
Exemplu
lacusta.in
4 5
3 4 5 7 9
6 6 3 4 4
6 3 3 9 6
6 5 3 8 2
lacusta.out
28
Explicație
Drumul este: