Minimum Path Sum: Taco Grid Problem

You are given an n × n grid containing positive integers. Your task is to find the minimum cost to move from the top-left cell to the bottom-right cell. At each step, you may only move either right or down. The cost of a path is the sum of all integers along the path.

Mathematically, if you denote the grid by \(G\) and define a path \(P\) from \((1,1)\) to \((n,n)\), then the cost is defined as:

[ Cost(P) = \sum_{(i,j) \in P} G_{i,j} ]

Your goal is to choose a path \(P\) that minimizes the cost.

Note: An efficient solution using dynamic programming is recommended for solving this problem.

inputFormat

The input is given from stdin and has the following format:

The first line contains an integer n (1 ≤ n ≤ 1000), the size of the grid.
Each of the next n lines contains n space-separated integers representing the row of the grid.

outputFormat

Output the minimum cost to travel from the top-left corner to the bottom-right corner. The result should be printed to stdout as a single integer.

3
1 2 3
4 5 6
7 8 9

21