Rezolvare PBinfo #4243

Un experiment urmăreşte comportarea unui şoricel pus într-o cutie dreptunghiulară, împărţită în n x m cămăruţe egale de formă pătrată. Fiecare cămăruţă conţine o anumită cantitate de hrană. Şoricelul trebuie să pornească din colţul (1, 1) al cutiei şi să ajungă în colţul opus (n, m), mâncând cât mai multă hrană. El poate trece dintr-o cameră în una alăturată (două camere sunt alăturate dacă au un perete comun), mănâncă toată hrana din cămăruţă atunci când intră. Se asemenea, nu va intra niciodată într-o cameră fără hrană.

Cerința

Stabiliţi care este cantitatea maximă de hrană pe care o poate mânca.

Date de intrare

Fișierul de intrare mouse.in conține pe prima linie două numere n şi m reprezentând numărul de linii respectiv numărul de coloane ale cutiei, iar pe următoarele n linii cele n x m numere reprezentând cantitatea de hrană existentă în fiecare cămăruţă, câte m numere pe fiecare linie, separate prin spaţii.

Date de ieșire

În fișierul de ieșire mouse.out se vor scrie pe prima linie două numere separate printr-un spaţiu: numărul de cămăruţe vizitate şi cantitatea de hrană maximă culeasă.

Restricții și precizări

• 1 ≤ n, m ≤ 100
• cantitatea de hrană din fiecare cămăruță este un număr natural cuprins între 1 și 100.

Exemplu:

mouse.in

2 4
1 2 6 3
3 4 1 2

mouse.out

7 21

Explicație