Minimum Path Sum

You are given an m × n integer matrix. Your task is to find the minimum path sum from the top-left corner (cell (1,1)) to the bottom-right corner (cell (m,n)).

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

The problem can be formulated using dynamic programming. Define \(dp[i][j]\) as the minimum sum of a path from the starting cell to cell \((i, j)\). The recursive relation is:

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

with the appropriate initial conditions.

inputFormat

The first line of input contains two integers m and n representing the number of rows and columns of the matrix respectively.

This is followed by m lines; each line contains n space-separated integers representing a row of the matrix.

outputFormat

Output a single integer, which is the minimum path sum from the top-left corner to the bottom-right corner of the matrix.

3 3
1 3 1
1 5 1
4 2 1

7