Minimum Path Sum in a Grid

You are given a 2D grid of non-negative integers. Your task is to calculate the minimum cost to travel from the top-left cell (1,1) to the bottom-right cell (n,m) of the grid. At any point, you can only move either right or down.

The cost of a path is the sum of all the numbers along the path. Formally, if \(grid[i][j]\) represents the cost at cell \((i, j)\), then the minimum path cost \(dp(n, m)\) is given by:

\[ dp(i,j) = \begin{cases} grid(1,1) & \text{if } i = 1 \text{ and } j = 1, \\ \min(dp(i-1,j), \; dp(i,j-1)) + grid(i,j) & \text{if } i > 1 \text{ or } j > 1. \end{cases} \]

Implement a solution that reads the grid from standard input and writes the result to standard output.

inputFormat

The first line contains two integers \(n\) and \(m\), the number of rows and columns in the grid, respectively. This is followed by \(n\) lines, each containing \(m\) non-negative integers representing the grid values, separated by spaces.

Example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Output a single integer: the minimum path cost from the top-left to the bottom-right of the grid.

Example:

7

## sample

3 3
1 3 1
1 5 1
4 2 1

7