Score : $500$ points

问题陈述

有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从顶部数第 $i$ 行，从左边数第 $j$ 列的单元格。

在这个网格上有 $N$ 个硬币，第 $i$ 个硬币可以通过经过单元格 $(R_i,C_i)$ 来拾取。

你的目标是从单元格 $(1,1)$ 开始，反复向下或向右移动一个单元格，同时尽可能多地拾取硬币，最终到达单元格 $(H,W)$。

找出你可以拾取的最大硬币数量，以及实现这一最大值的一条路径。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.

There are $N$ coins on this grid, and the $i$-th coin can be picked up by passing through the cell $(R_i,C_i)$.

Your goal is to start from cell $(1,1)$, repeatedly move either down or right by one cell, and reach cell $(H,W)$ while picking up as many coins as possible.

Find the maximum number of coins you can pick up and one of the paths that achieves this maximum.

Constraints

• $2\leq H,W \leq 2\times 10^5$
• $1\leq N \leq \min(HW-2, 2\times 10^5)$
• $1\leq R_i \leq H$
• $1\leq C_i \leq W$
• $(R_i,C_i)\neq (1,1)$
• $(R_i,C_i)\neq (H,W)$
• $(R_i,C_i)$ are pairwise distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$H$ $W$ $N$

$R_1$ $C_1$

$R_2$ $C_2$

$\vdots$

$R_N$ $C_N$

Output

Print two lines. The first line should contain the maximum number of coins you can pick up. The second line should contain one of the paths that achieves this maximum as a string of length $H+W-2$. The $i$-th character of this string should be D if the $i$-th move is downward, and R if it is rightward.

If there are multiple paths that maximize the number of coins picked up, you may print any of them.

Sample Input 1

3 4 4
3 3
2 1
2 3
1 4

Sample Output 1

3
DRRDR

As shown in the figure above, by moving $(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$, you can pick up three coins at $(2,1),(2,3),(3,3)$.

Sample Input 2

2 2 2
2 1
1 2

Sample Output 2

1
DR

The path RD is also acceptable.

Sample Input 3

10 15 8
2 7
2 9
7 9
10 3
7 11
8 12
9 6
8 1

Sample Output 3

5
DRRRRRRRRDDDDDRRDRDDRRR