Fișierul intrare/ieșire	lacusta.in, lacusta.out	Sursă	OJI 2005 clasa a 10-a
Autor	Nistor-Eugen Moț	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Lăcusta (clasa a 10-a)

Se consideră o matrice dreptunghiulară cu m linii și n 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 2m 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 m n, reprezentând numărul de linii și respectiv numărul de coloane ale matricei. Pe următoarele m linii este descrisă matricea, câte n 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

• 1 ≤ m, n ≤ 100
• Valorile elementelor matricei sunt numere întregi din intervalul [1, 255]

Exemplu