Minimum Energy Path

You are given a grid with N rows and M columns where each cell has an energy cost. Starting from the top-left corner, you can only move either to the right or down. Your task is to compute the minimum energy required to reach the bottom-right corner.

To solve this problem, you can use a dynamic programming approach by maintaining a dp table where dp[i][j] represents the minimum energy needed to reach cell (i, j). The transition is given by:

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

with the boundary conditions that the first row and the first column can only be reached from one direction.

inputFormat

The first line contains two integers N and M, separated by a space. Following this, there are N lines, each containing M integers separated by spaces, representing the energy cost of each cell.

outputFormat

Output a single integer: the minimum energy required to reach the bottom-right corner of the grid.## sample

3 3
1 3 1
1 5 1
4 2 1

7