Două persoane au inventat un joc cu următoarele reguli:

1. 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.
2. Î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ă).
3. Î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].

Exemple