Fișierul intrare/ieșire	pion.in, pion.out	Sursă	campion
Autor	Nistor-Eugen Moț	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.26 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	2.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Pion

Notă: Această problemă este o versiune mai grea a problemei pion de pe Campion.

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.

Determinați suma de bani maximă pe care o poate câștiga jucătorul care începe jocul, precum și traseul urmat de pion, știind că ambii jucători joacă optim.

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

În fișierul de ieșire pion.out se va scrie, pe prima linie, un număr reprezentând câștigul maxim al primului jucător. Pe a doua linie se va scrie un șir de litere „J” și „D” indicând mutările (în jos sau la dreapta) urmate de pion.

Restricții

• 1 ≤ m, n ≤ 5.000
• Numerele de pe ultima linie și coloană sunt întregi din intervalul [1, 60.000].
• Dacă la orice moment ambele mutări duc la același scor optim, jucătorii vor prefera mutarea în jos.

Exemplu

Explicație

Jucătorul 1 mută pionul în căsuța (1, 2). Jucătorul 2 mută pionul în căsuța (2, 2). Jucătorul 1 mută pionul în căsuța (2, 3). Jucătorul 2 mută pionul în căsuța (3, 3). Jucătorul 1 mută pionul în căsuța (4, 3).

Dacă jucătorul 1 ar începe jocul mutând la (2, 1), atunci jucătorul 2 ar răspunde mutând la (3, 1). De aici, jucătorul 1 n-ar putea obține decât scorul 7.