Minimum Path Resistance

You are given a grid with n rows and m columns. Each cell in the grid contains a positive integer representing the resistance at that cell. Your task is to find a path from the top-left cell to the bottom-right cell such that the total resistance (i.e. the sum of the cell resistances along the path) is minimized. You can only move either to the right or down at any step.

Let \(dp[i][j]\) represent the minimum resistance required to reach cell \((i+1, j+1)\) from the top-left cell. The recurrence relation for the dynamic programming solution is:

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

with the appropriate boundary conditions for the first row and first column. Solve the problem and output the minimum total resistance.

inputFormat

The input is given from stdin and has the following format:

n m
grid[0][0] grid[0][1] ... grid[0][m-1]
grid[1][0] grid[1][1] ... grid[1][m-1]
...
grid[n-1][0] grid[n-1][1] ... grid[n-1][m-1]

where n and m (1 \(\le\) n, m \(\le\) 1000) are the dimensions of the grid and each grid[i][j] is a positive integer.

outputFormat

Output a single integer to stdout representing the minimum total resistance to reach the bottom-right cell from the top-left cell.

3 3
1 3 1
1 5 1
4 2 1

7