Minimum Path Sum

Given an \(m \times n\) grid filled with non-negative integers, find a path from the top-left cell to the bottom-right cell which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time. Formally, if we denote the grid as \(grid\), the goal is to compute the minimum sum:

\[ \min_{\text{path}} \; \sum_{(i,j) \in \text{path}} grid_{i,j} \]

where a valid path starts at \(grid_{0,0}\) and ends at \(grid_{m-1,n-1}\). The integers \(m\) and \(n\) denote the number of rows and columns, respectively.

inputFormat

The input is given via standard input. The first line contains two integers \(m\) and \(n\), representing the number of rows and columns of the grid. The next \(m\) lines each contain \(n\) space-separated integers describing the grid values.

outputFormat

Output a single integer via standard output representing the minimum sum along a valid path from the top-left corner to the bottom-right corner.

3 3
1 3 1
1 5 1
4 2 1

7