mouse

Un experiment urmărește comportarea unui șoricel pus într-o cutie dreptunghiulară, împărțită în $m \times n$ 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, 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ă și nu intră niciodată într-o cameră în care a mai intrat înainte.

Cerință

Stabiliți care este cantitatea maximă de hrană pe care o poate mânca și traseul pe care îl poate urma pentru a culege această cantitate maximă.

Date de intrare

Fișierul de intrare mouse.in conține pe prima linie două numere $m$ și $n$ reprezentând numărul de linii respectiv numărul de coloane ale cutiei, iar pe următoarele $m$ linii cele $m \cdot n$ numere reprezentând cantitatea de hrană existentă în fiecare cămăruță, câte $n$ 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ă. Pe următoarele linii se va scrie un traseu posibil pentru cantitatea dată, sub formă de perechi de numere, începând cu $(1, 1)$ și terminând cu $(m, n)$.

Restricții și precizări

• Toate valorile din fișier sunt numere naturale între $1$ și $100$.
• Veți primi 40 de puncte pentru afișarea primelor două numere.

Exemplu

mouse.in

2 4
1 2 6 3
3 4 1 2

mouse.out

7 21
1 1
2 1
2 2
1 2
1 3
1 4
2 4

Explicație