Minimum Travel Time in a Grid

You are given a grid of size \(m \times n\) where each cell contains a non-negative integer representing the time needed to pass through that cell. The agent starts at the top-left corner (cell \((0,0)\)) and needs to reach the bottom-right corner (cell \((m-1,n-1)\)) by only moving right or down.

Your task is to compute the minimum total time required for the agent to travel from the start to the exit. The recurrence relation for the dynamic programming solution is given by:

[ \text{dp}[i][j] = \min(\text{dp}[i-1][j],, \text{dp}[i][j-1]) + \text{grid}[i][j] ]

with base conditions:

• \(\text{dp}[0][0] = \text{grid}[0][0]\)
• For the first row: \(\text{dp}[0][j] = \text{dp}[0][j-1] + \text{grid}[0][j]\)
• For the first column: \(\text{dp}[i][0] = \text{dp}[i-1][0] + \text{grid}[i][0]\)

Find and print the minimum travel time based on the given grid.

inputFormat

The first line contains two integers \(m\) and \(n\) (the number of rows and columns of the grid, respectively). The next \(m\) lines each contain \(n\) space-separated integers representing the grid.

outputFormat

Print a single integer representing the minimum travel time from the top-left to the bottom-right corner of the grid.

3 3
1 3 1
1 5 1
4 2 1

7