Теперь черепашке Кондратине надо узнать не только, сколько цветочков она может собрать, но и как ей построить свой маршрут для этого. Помогите ей!
Напомним, что Кондратине надо дойти от левого нижнего до правого верхнего угла, а передвигаться она умеет только вверх и вправо.
В первой строке даны размеры поля n и m (через пробел). Оба числа лежат в диапазоне от 1 до 1000. В следующих n строках задано поле. Каждая строка состоит из m символов 0 или 1 и завершается переводом строки. Если в клетке записана единица, то в ней растет цветочек.
Выведите в первой строке максимальное количество цветочков, которое сможет собрать Кондратина. Во второй строке выведите маршрут в виде последовательности символов «U» и «R», где «U» означает передвижение вверх, а «R» – передвижение вправо.
Если возможных оптимальных путей несколько, то выведите любой.
|
2 3 101 110 |
3 URR |
|
3 3 100 110 001 |
2 URR |