D. Пешка
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В некоторой клетке нижнего ряда шахматной доски стоит пешка. У нее есть всего два варианта хода: вверх и влево или вверх и вправо. Пешка может выбрать, с какой клетки нижнего ряда она начнет свое путешествие. На каждой клетке доски лежит от 0 до 9 горошин. Пешка хочет дойти до верхнего ряда, собрав как можно больше горошин. Так как там ей придется поделиться горошинами с k братьями, число горошин обязательно должно делиться на k + 1. Определите, какое наибольшее число горошин она сможет собрать, и какие ходы она должна для этого делать.

Пешка не может выбрасывать горошины, а также выходить за пределы доски. Когда пешка оказывается в какой-то клетке доски (включая первую и последнюю клетку пути), она обязательно берет все горошины.

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

В первой строке записаны три целых числа n, m, k (2 ≤ n, m ≤ 100, 0 ≤ k ≤ 10) — количество рядов и столбцов в шахматной доске, количество братьев пешки. Далее следует n строк по m цифр от 0 до 9 без пробелов — описание шахматной доски. Каждая клетка описывается одной цифрой — количество горошин в ней. Первая строка соответствует верхнему ряду, а последняя — нижнему.

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

Если невозможно добраться до верхнего ряда, собрав при этом число делящееся на k + 1 количество горошин, выведите -1.

Иначе, первая строка должна содержать одно число — какое наибольшее число горошин она сможет собрать, при условии, что это число должно делиться на k + 1. Вторая строка должна содержать одно число — номер столбца клетки на нижнем ряду, откуда пешка должна начать свое путешествие. Столбцы нумеруются слева направо натуральными числами начиная с 1. Третья строка должна содержать строку из n - 1 символов — описание ходов пешки. Если пешка должна пойти вверх и влево, выведите L, если вверх и вправо, выведите R. Если решений несколько, выведите любое.

Примеры
Входные данные
3 3 1
123
456
789
Выходные данные
16
2
RL
Входные данные
3 3 0
123
456
789
Выходные данные
17
3
LR
Входные данные
2 2 10
98
75
Выходные данные
-1