Minimum Path Cost

In this problem, you are given an ( m \times n ) grid (matrix) where each cell contains a non-negative integer representing a cost. Your task is to compute the minimum cost required to travel from the top-left corner to the bottom-right corner of the matrix. At any cell, you may only move either to the right or downward.

The recurrence relation for this problem is given by: [ dp[i][j] = matrix[i][j] + \min(dp[i-1][j],, dp[i][j-1]) ] with the initial condition ( dp[0][0] = matrix[0][0] ).

Your solution should read the input from stdin and output the answer to stdout.

inputFormat

The first line of input contains two integers m and n separated by a space, representing the number of rows and columns of the matrix, respectively.

This is followed by m lines each containing n space-separated integers representing the cost values of the matrix.

outputFormat

Output a single integer: the minimum cost to travel from the top-left to the bottom-right corner of the matrix.

3 3
1 3 1
1 5 1
4 2 1

7