Let us call the coin that can be collected by passing through square \((r,c)\) simply coin \((r,c)\).

Given \(k\) coins \((r_1,c_1),(r_2,c_2),\dots,(r_k,c_k)\), one can determine if there is a path that can collect all the coins as follows:

1. Sort the coins in ascending order of \((r,c)\). Here, \((r_i, c_i) < (r_j, c_j) \Leftrightarrow (r_i < r_j) \lor (r_i = r_j \land c_i < c_j)\). Let \(((r'_1,c'_1),(r'_2,c'_2),\dots,(r'_k,c'_k))\) be the resulting sequence.
2. There exists a path that can collect all the given \(k\) coins if and only if \(c'_1 \leq c'_2 \leq \dots \leq c'_k\).

Suppose that the given \(N\) coins are sorted in ascending order of \((r,c)\). Then, by the fact above, this problem is boiled down to finding a longest (weakly) increasing subsequence (LIS).

Given positive integer sequence \(c=(c_1,c_2,\dots,c_N)\), one can find the length of a LIS of \(c\) (not its length) by the following famous algorithm:

1. Prepare a length-\(N\) sequence \(d\) initialized with \(\infty\).
2. Do the following for \(i=1,2,\dots,N\).
   • For the minimum \(j\) with \(d_j > c_i\), replace \(d_j\) with \(c_i\).
3. The length of a LIS of \(c\) is the maximum \(j\) with \(d_j < \infty\).

Intuitively, each \(d_j\) manages the smallest last element of a length-\(j\) (weakly) increasing subsequence of \(c_1,c_2,\dots,c_i\) (or \(\infty\) if there is no such subsequence).

To find an example of LIS instead of its length only, let us modify the algorithm as follows.

1. Prepare a length-\(N\) sequence \(d\) initialized with \(\infty\).
2. Prepare a length-\(N\) sequence \(\text{id}\) and \(\text{pre}\).
3. Do the following for \(i=1,2,\dots,N\).
   • For the minimum \(j\) with \(d_j > c_i\), replace \(d_j\) with \(c_i\), and replace \(\text{id}_j\) with \(i\). If \(j > 1\), replace \(\text{pre}_i\) with \(\text{id}_{j-1}\) too.
4. The length of a LIS of \(c\) is the maximum \(j\) with \(d_j < \infty\).
5. Let \(l\) be the length of a LIS of \(c\). Consider a length-\(l\) sequence obtained by applying \((l-1)\) times the action \(i\mapsto \text{pre}_i\) to \(\text{id}_l\), namely \((\text{id}_l, \text{pre}_{\text{id}_l},\text{pre}_{\text{pre}_{\text{id}_l}},\dots)\). The reversal of this sequence is an example of a LIS of \(c\).

The fact that an example of LIS can be indeed obtained using this algorithm can be proved inductively. The complexity of this algorithm is \(O(N\log N)\), same as the original algorithm. (To find the minimum \(j\) in step \(3\), use binary search.) Thus, the problem has been solved.

Sample code (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';
}