Minimum Path Sum in a Grid

You are given a square grid (grid) of size (n \times n) where each cell contains a non-negative integer cost. The task is to compute the minimum path sum required to travel from the top-left cell to the bottom-right cell. You can only move either right or down at any step.

Formally, given a grid (grid), find a path from (grid_{0,0}) to (grid_{n-1,n-1}) that minimizes the sum of the cell values along the path. The solution should use dynamic programming to achieve an efficient result.

inputFormat

The first line of input contains an integer (n), the size of the grid. Each of the following (n) lines contains (n) space-separated integers representing the cost values of the grid.

outputFormat

Output a single integer which is the minimum path sum from the top-left cell to the bottom-right cell.## sample

2
1 3
2 4

7