3. Zatúlané cukríky

Kuko má rád sladkosti. Nepohrdne čokoládou, horalkou, ba ani čistým cukrom. No zo všetkého najradšej má rád cukríky. Takmer vždy má pri sebe otvorené vrecúško jeho obľúbených maškŕt.

Jedného krásneho dňa šiel ako každý správny matfyzák na prednášku. A ako každý správny vedúci samozrejme na poslednú chvíľu. No ako obiehal Zergbota s kofolou, potkol sa a celé balenie sa mu rozsypalo po chodbe.

Rád by ich čo najviac pozbieral späť do sáčku, no nemôže sa veľmi zdržať, keďže už aj tak mešká na prednášku. Preto vás požiadal o pomoc.

Úloha

Chodbu na matfyze si môžete predstaviť ako obdĺžnik \(n\times m\) dláždený štvorcovými kachličkami. Keď Kuko prejde cez kachličku, zoberie všetky cukríky, ktoré sú na nej vysypané. Začína v ľavom hornom rohu chodby, prednášku má v pravom dolnom. Keďže sa na ňu ponáhľa, tak sa k nej chce v každom kroku posunúť bližšie. Môže teda chodiť iba doprava alebo dole.

Vašou úlohou je zistiť, koľko najviac cukríkov vie Kuko vyzbierať a ako sa má hýbať aby sa mu to podarilo.

Úloha sa testuje na piatich sadách vstupov. Pre vyriešenie prvých \(2\) sád nemusíte vypisovať Kukovu cestu, stačí zistiť počet cukríkov. Za takýto program dostanete \(2\) body.

Pre jednotlivé testovacie sady platia nasledovné obmedzenia:

Formát vstupu

Na prvom riadku vstupu dostanete čísla \(n\) a \(m\) – rozmery chodby. Nasleduje \(n\) riadkov, každý obsahuje \(m\) čísel oddelených medzerou – počty cukríkov na jednotlivých kachličkách. Tieto čísla sú v rozsahu od \(1\) po \(10^6\).

Formát výstupu

Na prvý riadok vypíšte najväčší počet cukríkov, ktoré vie Kuko zozbierať. Na nasledulúci riadok vypíšte jeden reťazec bez medzier, reprezentujúci Kukovu trasu. Písmeno D označuje pohyb dole, písmeno R pohyb doprava. Ak existuje viacej optimálnych trás, vypíšte ľubovoľnú z nich.

Príklad

Input:

4 5
1 2 5 1 2
3 2 1 2 1
1 4 3 2 1
3 1 2 2 2

Output:

19
DRDRRDR