Minimum Delivery Time

You are given a matrix of nonnegative integers where each cell represents the delivery time required to pass through that cell. Your task is to find the minimum total delivery time to go from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (N-1, M-1)) of the matrix.

You can only move either right or down at any point in time.

The transition equation can be written in LaTeX as:

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

with the base case:

$$dp[0][0] = matrix[0][0]$$

Your goal is to compute dp[N-1][M-1], where N is the number of rows and M is the number of columns.

inputFormat

The first line contains two integers N and M, representing the number of rows and columns of the grid, respectively.

The next N lines each contain M space-separated integers representing the cost (delivery time) in each cell of the matrix.

You can assume that 1 ≤ N, M ≤ 1000 and each cell contains an integer between 0 and 1000.

outputFormat

Output a single integer, which is the minimum total delivery time from the top-left corner to the bottom-right corner.

## sample

3 3
1 3 1
1 5 1
4 2 1

7