Minimum Path Sum

You are given a matrix of integers with m rows and n columns. Your task is to find the minimum path sum from the top-left corner to the bottom-right corner. You can only move either right or down at any point in time.

Formally, let \(A_{i,j}\) denote the element in the \(i^{th}\) row and \(j^{th}\) column of the matrix. The task is to compute:

[ \text{dp}(i,j)=A_{i,j}+\min\begin{cases}\text{dp}(i-1,j),\ \text{dp}(i,j-1)\end{cases} ]

with the boundary conditions given by the first row and first column. The answer is \(\text{dp}(m-1,n-1)\).

This problem has been classified as hard.

inputFormat

The first line contains two space-separated integers \(m\) and \(n\), representing the number of rows and columns in the matrix respectively. Following that, there are \(m\) lines, each containing \(n\) space-separated integers denoting the matrix elements.

Example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Output the minimum path sum from the top-left to the bottom-right corner as a single integer.

## sample

3 3
1 3 1
1 5 1
4 2 1

7