U514748 摸个鱼鱼

小 C 是想象学竞赛的摸鱼怪。 这天，小 C 想象出了一个 $n \times m$ 的棋盘，每个格子上都写了一个非负整数。小 C 想象自己在左上角放了 $k$ 个棋子。接下来，每次小 C 可以把一颗棋子移动到相邻的位置（不能移出棋盘）。小 C 每把棋子移动到一个格子，分数就会增加这个格子上写的数字。 然而这实在太无趣了。于是小 C 想象了一条规则：当一个棋子进入一个格子，这个格子就会变得不稳定，所有棋子不能再**进入**这个不稳定的格子。 **请注意：棋子离开之后，这个格子仍然是不稳定的。** 小 C 想知道，对于给定的棋盘和棋子数，他能否把所有棋子从左上角移到右下角，如果可以，他应该如何移动，才能在把所有棋子移到右下角的情况下最大化他的分数。 为了避免歧义，小 C 在左上角和右下角上写的数字都为 $0$。

第一行三个整数 $n, m, k$。 接下来 $n$ 行，每行 $m$ 个非负整数。保证左上角和右下角的数都为 $0$。

如果不能把所有棋子移到右下角，只输出 $-1$。 如果可以，第一行一个整数，代表最大的分数。 接下来 $k$ 行，每行用 $\texttt{U D L R}$ 组成的字符串表示一个棋子的移动路线，其中 $\texttt{U D L R}$ 分别表示向上、下、左、右走。如果有多种可能的方案，输出一种即可。 由于 Special Judge 的局限性，当能求出最大分数，但是不能构造方案的时候，请在输出的分数后面加上 $k$ 个空行，这样如果输出的分数正确，仍有 $50\%$ 的得分。

### 数据范围 对于 $100\%$ 的数据，$1 \le n, m, k \le 500$ 且 $nm>1$。 对于 $30\%$ 的数据，$n, m \le 20$。 对于 $30\%$ 的数据，$k = 1$。 保证棋盘上数字的和不超过 $2^{31}-1$。 ### 小题 如果你输出的最大分数正确，你可以拿到该测试点 $50\%$ 的得分。 ### checker 将附件中的 `checker.cpp` 编译之后在命令行运行 ` ` 即可。