Problem statement: You are given a rectangular matrix matrix of size n×m, where each cell holds a number – the cost of passing through it. The turtle starts in cell (0, 0) and may only move right or down. Find the path from cell (0, 0) to (n-1, m-1) with the minimum total cost and print the sequence of steps.

Input format: The first line contains two numbers, n and m (1 ≤ n, m ≤ 1000). Then follow n lines, each containing m integers separated by spaces, where 0 ≤ matrix[i][j] ≤ 100.

Output format: In the first line print the minimum total cost, and in the second the sequence of characters R (right) and D (down) denoting the turtle's steps (for example: RRDRD).

Solution: The problem is solved with dynamic programming. A two-dimensional array dp is created, where dp[i][j] is the minimum cost of a path from cell (0,0) to cell (i,j). In addition, a parent array is built to reconstruct the route, where parent[i][j] stores the direction of the previous step ('R' if the move came from the cell on the left, and 'D' if from the one above).

Initial condition:

dp[0][0] = matrix[0][0]

For the remaining cells we pick the optimal move — from the cell above or from the left — while updating the parent of the current cell:

Once the dp array is filled, the value dp[n-1][m-1] is the minimum cost sought, and the parent array makes it possible to reconstruct the optimal path.

For example, given the matrix:

after the computation we get:

Path reconstruction: Start from cell (n-1, m-1) and, following the pointers in the parent array, walk back to cell (0, 0). The resulting sequence of steps is then reversed to print the optimal route.