Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×
G. Замкнутая матрица
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана матрица размера $$$n \times m$$$, состоящая из целых положительных чисел.

Вы можете выбрать любую начальную клетку матрицы. За один ход вы перемещаетесь либо вниз, либо вправо в матрице. При этом ход из ячейки $$$(n, j)$$$ матрицы вниз перемещает вас в ячейку $$$(1, j)$$$, а ход из ячейки $$$(i, m)$$$ вправо перемещает вас в ячейку $$$(i, 1)$$$.

Ваша задача — сделать ровно $$$n$$$ ходов вниз и ровно $$$m$$$ ходов вправо и вернуться в изначальную клетку так, чтобы никакая клетка матрицы не была посещена дважды (кроме начальной). Найдите такой способ выбрать начальную клетку и сделать $$$n+m$$$ ходов, как описано выше, чтобы сумма чисел в пройденных клетках была максимальна.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 1\,500$$$) — размеры матрицы.

Следующие $$$n$$$ строк содержат по $$$m$$$ целых положительных чисел, $$$i$$$-я из этих строк содержит числа $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$1 \le a_{i, j} \le 1\,000\,000$$$) — числа в $$$i$$$-й строке матрицы.

Выходные данные

В первой строке выведите максимальную сумму, которую возможно набрать с помощью $$$n$$$ ходов вниз и $$$m$$$ ходов вправо.

Во второй строке выведите два числа $$$r$$$ и $$$c$$$ — номер строки и номер столбца стартовой ячейки в оптимальном способе.

В последней строке выведите строку из $$$n+m$$$ символов, состоящую из ровно $$$n$$$ символов 'D' и ровно $$$m$$$ символов 'R', соответствующую оптимальной последовательности ходов. Символ 'D' соответствует ходу вниз, символ 'R' соответствует ходу вправо.

Если ответов несколько, выведите любой из них.

Примеры
Входные данные
2 2
1 2
3 4
Выходные данные
10
1 1
DRDR
Входные данные
3 3
1 2 3
4 5 6
7 8 9
Выходные данные
37
1 2
DRDRRD
Входные данные
3 3
9 1 1
9 9 9
9 1 1
Выходные данные
46
1 1
DRRDRD
Входные данные
3 7
74 68 24 42 27 1 81
57 67 49 40 1 92 83
34 88 86 45 32 48 24
Выходные данные
613
1 2
DDRRRRRDRR