AT_abc369_f [ABC369F] Gather Coins

[problemUrl]: https://atcoder.jp/contests/abc369/tasks/abc369_f 縦 $ H $ 行、横 $ W $ 列のグリッドがあります。 このグリッドの上から $ i $ 行目、左から $ j $ 列目にあるマスのことを $ (i,j) $ と表記します。 このグリッド上には $ N $ 枚のコインが落ちており、$ i $ 個目のコインはマス $ (R_i,C_i) $ を通ることで拾うことができます。 あなたの目標は、マス $ (1,1) $ から始めて下か右に $ 1 $ マス移動することを繰り返し、できるだけ多くのコインを拾いながらマス $ (H,W) $ まで行くことです。 あなたが拾うことのできるコインの枚数の最大値、およびそれを達成するための移動経路を $ 1 $ つ求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ N $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ \vdots $ $ R_N $ $ C_N $

$ 2 $ 行出力せよ。 $ 1 $ 行目には、あなたが拾うことのできるコインの枚数の最大値を出力せよ。 $ 2 $ 行目には、それを達成するための移動経路の $ 1 $ つを長さ $ 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) $ は互いに相異なる - 入力は全て整数 ### Sample Explanation 1 !\[\](https://img.atcoder.jp/abc369/8c45374379376c75b6cfd44cb8efeaf8.png) 上図のように $ (1,1)\rightarrow\ (2,1)\rightarrow\ (2,2)\rightarrow\ (2,3)\rightarrow\ (3,3)\rightarrow\ (3,4) $ と移動することで、$ (2,1),(2,3),(3,3) $ にある $ 3 $ 枚のコインを拾うことができます。 ### Sample Explanation 2 `RD` という移動経路も正解となります。