Minimum Energy Path

You are given a grid of size \(M \times N\) where each cell contains a non-negative integer representing the energy cost to enter that cell. Your task is to start from the top-left cell (\(1,1\)) and reach the bottom-right cell (\(M,N\)) while minimizing the total energy cost. You can only move either right or down at any point in time.

The energy cost for each step is defined by the following recurrence: \[ \text{dp}[i][j] = \min(\text{dp}[i-1][j],\, \text{dp}[i][j-1]) + \text{grid}[i][j] \] with the initial condition \(\text{dp}[1][1] = \text{grid}[1][1]\).

Compute and return the minimum total energy required to reach the bottom-right cell.

inputFormat

The input is provided via standard input (stdin) in the following format:

M N
row1_element1 row1_element2 ... row1_elementN
row2_element1 row2_element2 ... row2_elementN
... 
rowM_element1 rowM_element2 ... rowM_elementN

Where \(M\) and \(N\) are the number of rows and columns respectively, followed by \(M\) lines each containing \(N\) space-separated integers representing the grid.

outputFormat

Output via standard output (stdout) a single integer - the minimum total energy required to reach the bottom-right cell.

3 3
1 3 1
1 5 1
4 2 1

7