Minimum Congestion Route

You are given a grid of size \(m \times n\) representing the congestion levels on each block of a city. Your task is to determine the minimum total congestion level required to travel from the top-left corner (cell \( (1,1) \)) to the bottom-right corner (cell \( (m,n) \)). You are only allowed to move either right or down at any step.

More formally, given a matrix \( grid \) where \( grid[i][j] \) represents the congestion level at cell \( (i+1,j+1) \), you need to find a path from \( grid[0][0] \) to \( grid[m-1][n-1] \) such that the sum of the congestion levels along the path is minimized. The only moves allowed are to the cell immediately to the right or the cell immediately below.

The solution involves dynamic programming where you build a DP table \( dp \) such that \( dp[i][j] \) represents the minimum congestion sum to reach the cell \( (i+1,j+1) \). The recurrence relation is:

[ dp[i][j] = grid[i][j] + \min \begin{cases} dp[i-1][j] & \text{if } i > 0 \ dp[i][j-1] & \text{if } j > 0 \end{cases} ]

You are to implement a solution that reads input from standard input (stdin) and prints the result to standard output (stdout).

inputFormat

The input begins with a line containing two integers \( m \) and \( n \) representing the number of rows and columns respectively. This is followed by \( m \) lines, each containing \( n \) space-separated integers. These integers denote the congestion levels of each cell in the grid.

outputFormat

Output a single integer: the minimum total congestion level from the top-left to the bottom-right cell.

3 3
1 3 1
1 5 1
4 2 1

7