Cerinţa

Pe un deal frumos
De la Chinteni în jos
Îndelung privește
Și se tot gândește
Un student din anul doi
“Mai bine aș fi cioban, la oi!”

Și atunci merge la stăpânul stânii să se angajeze pe o funcție de conducere, adică pe job-ul de cioban. Vasile, stăpânul stânii, e și el absolvent de informatică, așa că la interviul de angajare îi dă următoarea problemă:

Dealul pe care se află stâna este împărțit in n*m sectoare și a fost cosit. În fiecare sector se află o cantitate cunoscută de fân. Trebuie să parcurgi dealul de la Nord la Sud, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i+1,j-1), (i+1,j) sau (i+1,j+1), dar fără a părăsi dealul. La trecerea printr-un sector, trebuie colectat tot fânul din acel sector. Care cantitatea totală maximă de fân pe care o poți colecta, parcurgând astfel dealul, știind că pleci din orice sector al liniei 1 (Nord) și te oprești în orice sector al liniei n (Sud), cu respectarea condițiilor de mai sus?

Studentul râde, deoarece a rezolvat probleme similare în clasa a XI-a. Atunci Vasile complică problema cu o condiție suplimentară: se poate trece dintr-un sector în altul conform direcțiilor de mai sus doar dacă cantitațile de fân din cele două sectoare au parități diferite.

Date de intrare

Fişierul de intrare chinteni.in conţine pe prima linie numerele n m. Următoarele n linii conțin câte m numere naturale, reprezentând cantitatea de fân din fiecare sector.

Date de ieşire

Fişierul de ieşire chinteni.out va conţine pe prima linie numărul V, reprezentând valoarea maximă a cantității de fân care poate fi adunată. Dacă nu se poate parcurge dealul în condițiile precizate în enunț, atunci se va afișa mesajul Imposibil.

Restricţii şi precizări

• 2 ≤ n,m ≤ 200
• cantitatea de fân din fiecare sector este un număr natural mai mic decât 100

Exemplu:

chinteni.in

4 5
5 8 3 7 7 
1 1 4 5 1 
5 8 9 1 7 
5 8 6 6 9 

chinteni.out

28

Explicație

Un traseu prin care se adună o cantitate de fân egală cu 28 este: