Куда именно идти

Найдите самый дешёвый путь из левой верхней клетки в правую нижнюю ходами вправо и вниз и выведите сам путь.

Путь записывается буквами: R — шаг вправо, D — шаг вниз. Если дешёвых путей несколько, подойдёт любой.

В первой строке числа $n$ и $m$ от $1$ до $1000$. В следующих $n$ строках по $m$ чисел от $0$ до $10^9$.

Строка из букв R и D. При $n = m = 1$ выведите пустую строку.

Для восстановления пути одной строки уже мало: нужна вся таблица. Идите от конца назад и на каждом шаге смотрите, из какой соседней клетки вы могли прийти, — та, у которой записана меньшая стоимость.