Minimum Cost Path in a Grid

You are given an (N \times N) grid where each cell contains a cost. Your task is to find the minimum cost required to travel from the top-left cell (0, 0) to the bottom-right cell (N-1, N-1) by only moving either right or down at any step.

The problem can be formulated using dynamic programming. Let (dp[i][j]) denote the minimum cost to reach cell ((i, j)). The recurrence relation is given by:
(dp[i][j] = \min{ dp[i-1][j],\ dp[i][j-1] } + cost(i,j)) for (i, j > 0).

Compute (dp[N-1][N-1]) as the answer.

inputFormat

The first line contains an integer (N), the size of the grid. The following (N) lines each contain (N) space-separated integers representing the cost of each cell.

outputFormat

Output a single integer representing the minimum cost to reach the bottom-right cell from the top-left cell.## sample

3
1 3 1
1 5 1
4 2 1

7