以下、マス \((r,c)\) を通ることで拾うことのできるようなコインのことを単にコイン \((r,c)\) と呼びます。

ある \(k\) 個のコイン \((r_1,c_1),(r_2,c_2),\dots,(r_k,c_k)\) について、これらのコインを全て拾えるような移動経路が存在するかどうかは、以下のようにして判定できます。

1. これらのコインを \((r,c)\) の昇順でソートする。なおここで、\((r_i, c_i) < (r_j, c_j) \Leftrightarrow (r_i < r_j) \lor (r_i = r_j \land c_i < c_j)\) である。これによって得られた列を \(((r'_1,c'_1),(r'_2,c'_2),\dots,(r'_k,c'_k))\) とおく。
2. \(c'_1 \leq c'_2 \leq \dots \leq c'_k\) である場合、またその場合に限り、与えられた \(k\) 個のコインを全て拾えるような移動経路が存在する。

入力で与えられる \(N\) 枚のコインが \((r,c)\) の昇順にソートされていることを仮定します。すると、上記の事実より、本問題は数列 \(c\) の最長 (広義) 増加部分列 (LIS) の一例を求める問題に帰着されます。

与えられた正整数列 \(c=(c_1,c_2,\dots,c_N)\) に対し、\(c\) の LIS の長さ（LIS 自体ではない）を求めるアルゴリズムとして以下のような有名なアルゴリズムがあります。

1. 長さ \(N\) の数列 \(d\) を用意し、その全ての要素を \(\infty\) で初期化する。
2. \(i=1,2,\dots,N\) の順に以下を行う。
   • \(d_j > c_i\) を満たす最小の \(j\) に対して、\(d_j\) を \(c_i\) で更新する。
3. \(c\) の LIS の長さは、\(d_j < \infty\) を満たす最大の \(j\) の値である。

意味合いとしては、このアルゴリズムにおける各 \(d_j\) は、\(c_1,c_2,\dots,c_i\) の中で作れる長さ \(j\) の (広義) 増加部分列の末尾の要素の最小値 (そのような部分列が存在しないならば \(\infty\)) を管理しています。

LIS の長さだけでなくその一例を求めるために、以下のようにアルゴリズムを少し修正します。

1. 長さ \(N\) の数列 \(d\) を用意し、その全ての要素を \(\infty\) で初期化する。
2. 長さ \(N\) の数列 \(\text{id},\text{pre}\) を用意する。
3. \(i=1,2,\dots,N\) の順に以下を行う。
   • \(d_j > c_i\) を満たす最小の \(j\) に対して、\(d_j\) を \(c_i\) で更新し、\(\text{id}_j\) を \(i\) で更新する。\(j > 1\) ならば、更に \(\text{pre}_i\) を \(\text{id}_{j-1}\) で更新する。
4. \(c\) の LIS の長さは、\(d_j < \infty\) を満たす最大の \(j\) の値である。
5. \(c\) の LIS の長さを \(l\) として、\(\text{id}_l\) に \(i\mapsto \text{pre}_i\) を \(l-1\) 回作用させることで得られる長さ \(l\) の数列 \((\text{id}_l, \text{pre}_{\text{id}_l},\text{pre}_{\text{pre}_{\text{id}_l}},\dots)\) を考える。この数列を反転させたものは \(c\) の LIS の一例である。

このアルゴリズムによって実際に \(c\) の LIS の一例が得られることは、帰納法を用いて証明できます。また、このアルゴリズムの計算量は、元のアルゴリズムの計算量と同じく \(O(N\log N)\) です（ステップ \(3\) における最小の \(j\) の発見には二分探索を用いるものとする）。よって本問題を解くことができました。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vector<pair<int, int>> coins;
    for (int i = 0; i < n; i++) {
        int r, c;
        cin >> r >> c;
        coins.emplace_back(r, c);
    }
    sort(coins.begin(), coins.end());
    vector<int> dp(n, 1e9), id(n, -1), pre(n);
    for (int i = 0; i < n; i++) {
        int it = upper_bound(dp.begin(), dp.end(), coins[i].second) - dp.begin();
        dp[it] = coins[i].second;
        id[it] = i;
        pre[i] = (it ? id[it - 1] : -1);
    }
    int m = n - 1;
    while (id[m] == -1) --m;
    vector<pair<int, int>> path = {{h, w}};
    int now = id[m];
    while (now != -1) {
        path.push_back(coins[now]);
        now = pre[now];
    }
    path.emplace_back(1, 1);
    reverse(path.begin(), path.end());
    string s;
    for (int i = 0; i < (int) path.size() - 1; i++) {
        int d = path[i + 1].first - path[i].first;
        int r = path[i + 1].second - path[i].second;
        while (d--) s.push_back('D');
        while (r--) s.push_back('R');
    }
    cout << m + 1 << '\n' << s << '\n';
}