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。
若存在多个可行解，输出任意一个即可。