Minimum Path Time in a Grid

You are given a grid with n rows and m columns. Each cell of the grid contains a non-negative integer representing the time required to pass through that cell. Your task is to find the minimum total time needed to travel from the top-left cell to the bottom-right cell. You may only move either down or right at any point in time.

The problem can be formulated as finding a path from the starting point \( (1,1) \) to the destination \( (n,m) \) such that the sum of the values along the path is minimized. Use the following recurrence in your solution: \[ \text{dp}[i][j] = \min(\text{dp}[i-1][j],\, \text{dp}[i][j-1]) + \text{grid}[i][j] \] with appropriate initialization along the top row and left column.

Note: The grid indices provided in the input are 1-indexed conceptually, but while implementing the solution, you can use 0-indexed arrays.

inputFormat

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns respectively. Following this, there are n lines, each containing m space-separated integers, representing the grid.

Example:

3 4
1 3 1 2
2 1 3 1
4 2 1 3

outputFormat

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

Example Output:

10

## sample

3 4
1 3 1 2
2 1 3 1
4 2 1 3

10

</p>