Minimum Effort Path in a Grid

Problem Statement:

You are given a grid of non-negative integers with (n) rows and (m) columns. Your task is to find the minimum effort required to travel from the top-left corner to the bottom-right corner of the grid. At each step, you are only allowed to move either right or down.

The effort of a path is defined as the sum of all numbers along the path. Formally, let (dp[i][j]) denote the minimum effort required to reach cell ((i, j)). Then for (i, j > 0), the following recurrence holds:
[ dp[i][j] = \min(dp[i-1][j],; dp[i][j-1]) + grid[i][j] ]

Initialize the boundaries as follows:
[ dp[0][j] = dp[0][j-1] + grid[0][j], \quad dp[i][0] = dp[i-1][0] + grid[i][0] ]

Compute and output (dp[n-1][m-1]), which is the minimum effort required to reach the bottom-right corner of the grid.

inputFormat

The input is read from standard input (stdin).

The first line contains two integers (n) and (m), representing the number of rows and columns in the grid, respectively. The next (n) lines contain (m) space-separated integers each, representing the grid.

outputFormat

Output a single integer to standard output (stdout), which is the minimum effort required to traverse the grid from the top-left to the bottom-right corner.## sample

3 3
1 3 1
1 5 1
4 2 1

7