Minimum Path in a Grid

You are given a grid of size \(N \times M\) where each cell contains a non-negative cost. Your task is to find the minimum cost path from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((N-1, M-1)\)). You may only move either right (R) or down (D) at any step.

The cost of a path is the sum of the costs of the visited cells. The recurrence relation used is:

\(\text{dp}[i][j] = \text{grid}[i][j] + \min(\text{dp}[i-1][j],\, \text{dp}[i][j-1])\)

If there is only one cell in the grid, output its cost and an empty path.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of rows and columns in the grid. Each of the next \(N\) lines contains \(M\) space-separated integers representing the cost in each cell of the grid.

outputFormat

The output consists of two lines. The first line contains the minimum cost to reach the bottom-right cell. The second line contains the path represented as a sequence of characters ('R' for right and 'D' for down) separated by a space. If no moves are needed (i.e. for a single cell grid), output an empty line for the path.

## sample

3 3
1 3 1
1 5 1
4 2 1

7
R R D D

</p>