Задача №112612. Черепаха и монеты
Черепаха хочет переползти из левого верхнего угла поля размером N на M клеток ( 2 ≤ N , M ≤ 1000 ) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Кроме того, проходя через каждую клетку, Черепаха получает (или теряет) несколько золотых монет (это число известно для каждой клетки).
Определите, какое максимальное количество монет может собрать Черепаха по пути и как ей нужно идти для этого.
В первой строке вводятся два натуральных числа: N и M ( 2 ≤ N , M ≤ 1000 ), разделённые пробелом. В каждой из следующих N строк записаны через пробел по M чисел, которые обозначают количество монет, получаемых Черепашкой при проходе через каждую клетку. Если это число отрицательное, Черепашка теряет монеты.
В первой строке программа должна вывести наибольшее количество монет, которое может собрать Черепаха. Во второй строке без пробелов выводятся команды, которые нужно выполнить Черепахе: буква 'R' (от слова right ) обозначает шаг вправо, а буква 'D' (от слова down ) – шаг вниз.
3 3 0 2 -3 2 -5 7 1 2 0
6 RRDD