Minimum Energy Path

You are given an (N \times M) grid where each cell contains an energy value. Your task is to find a path from the top-left to the bottom-right cell such that the total energy cost is minimized. You can only move either right or down from a cell. The cost of a path is the sum of the values of the cells visited along the way.

Formally, if (grid[i][j]) represents the energy at cell ((i,j)), you need to compute the minimum value of the sum (\sum_{(i,j) \in path} grid[i][j]) for a path starting at ((0,0)) and ending at ((N-1,M-1)), with the allowed moves being right ((j+1)) and down ((i+1)).

inputFormat

The first line of the input contains two space-separated integers (N) and (M), representing the number of rows and columns of the grid. The following (N) lines each contain (M) space-separated integers representing the energy values of the grid.

outputFormat

Output a single integer representing the minimum energy required to reach the bottom-right corner from the top-left corner.## sample

3 3
1 3 1
1 5 1
4 2 1

7