CF41D.Pawn

On some square in the lowest row of a chessboard a stands a pawn. It has only two variants of moving: upwards and leftwards or upwards and rightwards. The pawn can choose from which square of the lowest row it can start its journey. On each square lay from 0 to 9 peas. The pawn wants to reach the uppermost row having collected as many peas as possible. As there it will have to divide the peas between itself and its k brothers, the number of peas must be divisible by k + 1. Find the maximal number of peas it will be able to collect and which moves it should make to do it.

The pawn cannot throw peas away or leave the board. When a pawn appears in some square of the board (including the first and last square of the way), it necessarily takes all the peas.

在国际象棋棋盘最底行的某个方格中放置一枚兵（pawn）。它仅有两种移动方式：向左上方或向右上方移动。兵可以自由选择从最底行的哪一个方格出发。每个方格上放置有 $0$ 至 $9$ 粒豌豆。兵希望到达最顶行，并尽可能多地收集豌豆。但由于抵达后需将所有豌豆平均分给自身及其 $k$ 个兄弟，因此所收集豌豆总数必须能被 $k+1$ 整除。请找出兵所能收集到的最大豌豆数量，以及实现该目标所需的具体移动路径。

兵既不能丢弃豌豆，也不能移出棋盘边界。当兵进入棋盘上的任一格（包括路径的起点与终点）时，必须取走该格中的全部豌豆。

The first line contains three integers n, m, k (2 ≤ n, m ≤ 100, 0 ≤ k ≤ 10) — the number of rows and columns on the chessboard, the number of the pawn's brothers. Then follow n lines containing each m numbers from 0 to 9 without spaces — the chessboard's description. Each square is described by one number — the number of peas in it. The first line corresponds to the uppermost row and the last line — to the lowest row.

第一行包含三个整数 $n$、$m$、$k$（$2 \leq n, m \leq 100$，$0 \leq k \leq 10$）—— 分别表示棋盘的行数、列数以及该兵卒的兄弟数量。接下来是 $n$ 行，每行包含 $m$ 个 $0$ 到 $9$ 的数字（数字间无空格）—— 描述棋盘。每个方格用一个数字表示——即该方格中豌豆的数量。第一行对应棋盘最上方的一行，最后一行对应棋盘最下方的一行。

If it is impossible to reach the highest row having collected the number of peas divisible by k + 1, print -1.

Otherwise, the first line must contain a single number — the maximal number of peas the pawn can collect given that the number must be divisible by k + 1. The second line must contain a single number — the number of the square's column in the lowest row, from which the pawn must start its journey. The columns are numbered from the left to the right with integral numbers starting from 1. The third line must contain a line consisting of n - 1 symbols — the description of the pawn's moves. If the pawn must move upwards and leftwards, print L, if it must move upwards and rightwards, print R. If there are several solutions to that problem, print any of them.

如果无法在收集到的豌豆数量能被 $k+1$ 整除的前提下到达最上方一行，则输出 -1。

否则，第一行输出一个整数——在满足所收集豌豆总数能被 $k+1$ 整除的前提下，卒所能收集到的最大豌豆数量；
第二行输出一个整数——卒必须出发的起始位置所在列号（位于最下方一行），列号从左至右依次用正整数编号，起始为 1；
第三行输出一个长度为 $n-1$ 的字符串——描述卒的移动路径：若向上且向左移动，输出 L；若向上且向右移动，输出 R。
若存在多个可行解，输出任意一个即可。