Minimum Cost Path

You are given a square grid of size n × n where each cell contains a non-negative integer representing the cost to enter that cell. Your task is to compute the minimum cost required to travel from the top-left corner (cell (0,0)) to the bottom-right corner (cell (n-1, n-1)). You are only allowed to move either to the right or down at each step.

A typical dynamic programming solution for this problem uses the recurrence relation: $$dp[i][j] = grid[i][j] + \min(dp[i-1][j],\, dp[i][j-1])$$ with the appropriate initialization at the boundaries.

Compute and output the minimum cost for the given grid.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer n representing the number of rows (and columns) in the grid.
2. n lines follow, each containing n space-separated integers representing the cost values of the grid.

outputFormat

Output a single integer which is the minimum cost to travel from the top-left to the bottom-right corner of the grid. The output is written to standard output (stdout).

3
1 3 1
1 5 1
4 2 1

7