Minimum Path Sum

You are given a grid of size M × N filled with non-negative integers. Your task is to find a path from the top-left corner to the bottom-right corner such that the sum of the numbers along the path is minimized. You are only allowed to move either right or down at any point in time.

The problem can be formulated as follows:

Given a grid \( board \) of dimensions \( M \) rows and \( N \) columns, find a path from \( board[0][0] \) to \( board[M-1][N-1] \) that minimizes the sum:

\[ \min_{path} \sum_{(i,j) \in path} board[i][j] \]

where the allowed moves are right: \((i, j) \rightarrow (i, j+1)\) and down: \((i, j) \rightarrow (i+1, j)\).

inputFormat

The input is given via stdin in the following format:

M N
row1_elem1 row1_elem2 ... row1_elemN
row2_elem1 row2_elem2 ... row2_elemN
... 
rowM_elem1 rowM_elem2 ... rowM_elemN

Here, the first line contains two integers, M and N, representing the number of rows and columns in the grid. The next M lines each contain N space-separated integers representing the grid values.

outputFormat

Output a single integer via stdout which is the minimum sum of a valid path from the top-left to the bottom-right corner of the grid.

## sample

3 3
1 3 1
1 5 1
4 2 1

7

</p>