D - ENEM

ENEM je hra pre dvoch hráčov, ktorá sa hrá na štvorčekovanom papieri veľkosti NxM. Na začiatku hry sa do každého z políčok napíše nejaké(náhodné) prirodzené číslo.

• Prvý hráč (povinne) začína tým, že ofarbí ľavé horné políčko papiera.
• Druhý hráč potom ofarbí susedné políčko napravo, alebo dole (od práve ofarbeného políčka).
• Opať prvý hráč ofarbí políčko napravo, alebo dole (od práve ofarbeného políčka).
• Takto hra pokračuje, až kým sa neofarbí pravé dolné políčko papiera, čím hra končí.

Jankovi sa hra zapáčila a rýchlo si vymyslel svoju stratégiu: "Ak mám na výber, tak vždy ofarbím políčko, ktoré má väčšiu hodnotu. V prípade, že aj pravé aj dolné políčko majú rovnaké hodnoty, ofarbím dolné políčko."
Na obrázku sú znázornené dve ukončené hry, kde prvý(červený) hráč hral Jankovou stratégiou.

Úloha

Vstup

• Prvý riadok bude obsahovať prirodzené čísla N M zodpovedajúce rozmerom papiera (1≤N≤100,1≤M≤100).
• Každý z nasledujúcich N riadkov bude obsahovať M kladných celých čísel(≤100) odpovedajúcim hodnote políčka na príslušnej pozícii.

Výstup

Príklad

Príklad vstupu

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

Príklad výstupu

1
-6
2
0