В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, или по диагонали вправо вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы. Но на некоторые клетки Черепашке запретили наступать.
Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наименьшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.
Входные данные
В первой строке входных данных записаны два натуральных числа N и M, — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Дальше идет число k - количество клеток на которые наступать нельзя. И наконец k строчек в каждой из которых находится пара значений - номер строки и номер столбца ячейки, на которую наступать черепашке нельзя.
Выходные данные
Первая строка выходных данных содержит минимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать букву D, означающую передвижение вниз или букву R, означающую передвижение направо, или B при перемещении по диагонали вниз вправо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 2 3 4
2 3 4 5
3 4 5 6
1
3 3
|
13
RBB
|