Minimum Path Sum

Given a square grid of size (N \times N) filled with positive integers, your task is to determine the minimum path sum from the top-left corner to the bottom-right corner. You may only move either right or down at any step.

In mathematical terms, if we define (dp[i][j]) as the minimum path sum to reach cell ((i, j)), then the recurrence relation is given by:
(dp[i][j] = grid[i][j] + \min(dp[i-1][j],; dp[i][j-1]))
with initial conditions (dp[0][0] = grid[0][0]) and appropriate boundary conditions for the first row and column.

inputFormat

The input is taken from standard input (stdin). The first line contains an integer (N) denoting the size of the grid. The following (N) lines each contain (N) space-separated positive integers representing the grid.

outputFormat

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

3
1 3 1
1 5 1
4 2 1

7