Черепаха хоче переповзти з лівого верхнього кута поля розміром \(N\) на \(M\) клітин ( \(2 \le N , M \le 1000\) ) у правий нижній. За один крок вона може переміститися на сусідню клітину праворуч або сусідню клітину вниз. Крім того, проходячи через кожну клітину, Черепаха отримує (або втрачає) кілька золотих монет (це число відоме для кожної клітини).

Визначте, яку максимальну кількість монет може зібрати Черепаха по дорозі та як їй потрібно йти для цього.

Формат вхідних даних

У першому рядку вводяться два натуральні числа: \(N\) і \(M\) ( \(2 \le N , M \le 1000\) ), розділені пробілом.

У кожному з наступних \(N\) рядків записані через пробіл по \(M\) чисел, які позначають кількість монет, що отримують Черепашка при проході через кожну клітину. Якщо це число від'ємне, то Черепашка втрачає монети.

Формат вихідних даних

У першому рядку програма має вивести найбільшу кількість монет, яку може зібрати Черепаха.

У другому рядку без пробілів виводяться команди, які потрібно виконати Черепаху: літера 'R' (від слова right) позначає крок управо, а літера 'D' (від слова down) - крок вниз.

Приклад вхідних даних

3 3
0 2 -3
2 -5 7
1 2 0

Приклад вихідних даних

6
RRDD