AT_abc369_f [ABC369F] Gather Coins

有一个高 $H$ 行、宽 $W$ 列的网格。我们用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。 在这个网格上有 $N$ 枚硬币，第 $i$ 枚硬币可以通过经过格子 $(R_i,C_i)$ 来捡到。 你的目标是从格子 $(1,1)$ 出发，每次只能向下或向右移动一格，尽可能多地捡到硬币，最终到达格子 $(H,W)$。 请你求出最多可以捡到多少枚硬币，并输出一种能够达到这个最大值的移动路径。

输入通过标准输入给出，格式如下： > $H$ $W$ $N$ $R_1$ $C_1$ $R_2$ $C_2$ $\cdots$ $R_N$ $C_N$

输出两行。第一行输出你最多可以捡到的硬币数量。第二行输出一种能够实现该最大值的移动路径，用一个长度为 $H+W-2$ 的字符串表示。第 $i$ 个字符表示第 $i$ 次移动，若向下移动则为 `D`，若向右移动则为 `R`。 如果存在多条能够捡到最多硬币的路径，输出其中任意一条均可。

### 限制条件 - $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)$ 互不相同 - 输入均为整数 ### 样例解释 1  如上图所示，按照 $(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$ 的路径移动，可以捡到 $(2,1)$、$(2,3)$、$(3,3)$ 这三个格子的硬币。 ### 样例解释 2 `RD` 这样的移动路径也是正确答案。 由 ChatGPT 4.1 翻译