Două persoane au inventat un joc cu următoarele reguli:
Spaţiul de joc este o matrice cu m+1 linii şi n+1 coloane. Numerotarea liniilor şi a coloanelor se face începând de la 1. Linia m+1 şi coloana n+1 conţin numere întregi strict pozitive.
În poziţia (1,1) se găseşte un pion pe care jucătorii îl deplasează alternativ într-o poziţie învecinată. Sunt permise doar deplasări din poziţia (i,j) în poziţia (i+1,j) sau (i,j+1) cu condiţia i≤m şi j≤n (deci pionul ajuns pe ultima linie sau ultima coloană nu se mai deplasează).
În momentul când pionul nu se mai poate deplasa, jucătorul care a făcut prima mutare primeşte de la celălalt o sumă de bani egală cu numărul de pe poziţia în care a ajuns.
Cerinţă
Determinaţi suma de bani maximă pe care o poate câştiga jucătorul care începe jocul ştiind că celălalt face mutările cele mai avantajoase pentru el.
Date de intrare
Fişierul de intrare pion.in conţine pe prima linie numerele m şi n, pe linia a doua n numere întregi, reprezentând valorile de pe linia m+1 coloanele 1 - n, iar pe linia a treia m numere reprezentând valorile de pe coloana n+1, liniile 1 – m. Pe poziţia (m+1,n+1) putem considera că se află numărul 0, poziţia fiind inaccesibilă, în condiţiile jocului.
Date de ieşire
Fişierul de ieşire pion.out va conţine o singură linie pe care va fi scris un număr reprezentând câştigul maxim al primului jucător.
Restricţii
2 <= m, n <= 200
Numerele de pe ultima linie şi coloană sunt întregi din intervalul [1, 5000].