Minimum Travel Time in a Grid

You are given a grid of size (n \times m) where each cell contains a positive integer representing the travel time through that cell. Your task is to determine the minimum total travel time required for an autonomous car to travel from the top-left cell ((0, 0)) to the bottom-right cell ((n-1, m-1)). The car can only move either to the right or downward.

The dynamic programming recurrence is given by:

[ dp[i][j] = \min(dp[i-1][j],; dp[i][j-1]) + grid[i][j] ]

with the boundary conditions:

[ dp[0][j] = dp[0][j-1] + grid[0][j] \quad \text{for } j \ge 1, \quad dp[i][0] = dp[i-1][0] + grid[i][0] \quad \text{for } i \ge 1. ]

Your solution must read input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of multiple lines:

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

outputFormat

Output a single integer which is the minimum travel time to get from the top-left to the bottom-right cell in the grid.## sample

3 3
1 3 1
1 5 1
4 2 1

7