Minimum Cleaning Time

You are given an n x m grid where each cell contains a non-negative integer representing the cleaning time required for that cell. A cleaning robot starts at the top-left cell (cell (1,1)) and aims to reach the bottom-right cell (cell (n,m)).

The robot can only move either to the right or down at any step. Your task is to compute the minimum total cleaning time required for the robot to reach its destination.

A dynamic programming approach can be used to solve this problem. The recurrence relation is given by:

$$ dp[i][j] = \min(dp[i-1][j],\, dp[i][j-1]) + grid[i][j] $$

where \(dp[i][j]\) represents the minimum cleaning time to reach cell \((i,j)\) from the starting cell.

inputFormat

The input is read from stdin in the following format:

• The first line contains two integers n and m (1 ≤ n, m), which represent the number of rows and columns of the grid, respectively.
• Each of the next n lines contains m space-separated integers representing the cleaning times of the grid cells.

outputFormat

Output a single integer which is the minimum total cleaning time required for the robot to move from the top-left cell to the bottom-right cell. The result should be printed to stdout.

3 3
1 3 1
1 5 1
4 2 1

7