收集金币

题目描述

有一个 $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$
$\vdots$
$R_N$ $C_N$

输出格式

输出两行。

第一行输出最多能拾取的金币数量。

第二行输出能达到该最大值的一条路径，为一个长度为 $H+W-2$ 的字符串。 若第 $i$ 次移动是向下，则该字符串第 $i$ 个字符为 D；若向右，则为 R。

若有多个能拾取最多金币的路径，输出其中任意一个即可。

样例

3 4 4
3 3
2 1
2 3
1 4

3
DRRDR

例如，按 $(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$ 移动，可以在 $(2,1),(2,3),(3,3)$ 处拾取 3 枚金币。

2 2 2
2 1
1 2

1
DR

路径 RD 也是可以的。

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

5
DRRRRRRRRDDDDDRRDRDDRRR

数据范围

• $2\le H,W \le 2\times 10^5$
• $1\le N \le \min(HW-2, 2\times 10^5)$
• $1\le R_i \le H$
• $1\le C_i \le W$
• $(R_i,C_i)\neq (1,1)$
• $(R_i,C_i)\neq (H,W)$
• $(R_i,C_i)$ 两两互不相同。
• 所有输入值均为整数。

提示

答案不唯一，输出任意合法解即可。