题目描述

有一个 $n$ 行 $m$ 列的二维网格。我们用 $(r, c)$ 表示这个二维迷宫中从上到下第 $r$ 行，从左到右第 $c$ 列的格子。

每个格子上都有一个数字，其中格子 $(i, j)$ 上的数字是 $a_{i,j}$。

Lucas 一开始在网格的左上角 $(1, 1)$ 处，他要到达网格的右下角 $(n, m)$ 处。

每次移动，Lucas 都只能从当前所在的格子 向右 或 向下 移动到与它相邻的那个格子中。

Lucas 最终会有一个得分，这个得分定义为 Lucas 在移动过程中到达过的所有格子上的数字之和（包括 $a_{1, 1}$ 和 $a_{n,m}$）。

请你帮助 Lucas 设计一个移动路线，使得他的得分最大。并输出这个移动方案。

输入格式

第一行，两个整数 $n$ 和 $m$，以一个空格分隔。

接下来 $n$ 行，每行包含 $m$ 个整数，表示每个格子上的数字。其中，第 $i$ 行的第 $j$ 个数字表示 $a_{i, j}$。

输出格式

输出共两行。

第一行，一个整数，表示你的最大得分。

第二行，输出一行字符串，为一个长度为 $n+m-2$ 的字符串，表示你的最优移动方案。这个字符串需要由字符 R 和 D 构成。

• 若字符串的第 $i$ 个字符是 R，表示你的第 $i$ 次移动是向右移动；
• 若字符串的第 $i$ 个字符是 D，表示你的第 $i$ 次移动是向下移动。

由于可能存在多个移动方案的代价都是最大的。所以这里要求你输出**“优先往右走”**的最优方案。也就是说：

• 如果 方案A 和 方案B 都是最优方案，但是两个方案第一次不同时，方案A 是往右走，而 方案B 是往下走，则 方案A 比 方案B 更优。

样例

3 3
1 1 1
1 1 1
1 1 1

RRDD

4 5
3 5 2 1 7
2 6 3 4 2
1 3 2 5 1
7 1 5 2 3

31
RDRRDDR

5 3
-2 3 -5
-5 1 8
-7 -2 -6
-1 -5 -3
-4 0 -2

-1
RDRDDD

说明/提示

数据规模与约定

数据规模与约定

• 对于 $20\%$ 的数据，$n, m \le 10$，$| a_{i,j} | \le 10$
• 对于 $40\%$ 的数据，$n, m \le 100$，$| a_{i,j} | \le 1000$
• 对于 $100\%$ 的数据，$1 \le n, m \le 1000$ 且 $n + m \gt 2$，$| a_{i,j} | \le 10^9$