Minimum Mail Delivery

You are given an integer n and an n x n grid. Each cell of the grid contains a non-negative integer representing the amount of mail to be delivered at that cell.

Your task is to determine the minimum total amount of mail that needs to be delivered when moving from the top-left corner (starting point) to the bottom-right corner (destination) of the grid. You can only move either to the right or downward at each step.

The path cost is defined as the sum of the values of all the visited cells including the starting and ending cells.

Note: The grid is indexed from 0 and the movement is only allowed in two directions: right and down.

Hint: Use dynamic programming to solve the problem.

inputFormat

The first line of input contains a single integer n representing the size of the grid.

The next n lines each contain n space-separated integers representing the grid.

For example:

3
1 3 1
1 5 1
4 2 1

outputFormat

Output a single integer which is the minimum total mail delivery cost from the top-left to the bottom-right of the grid.

For the sample input above, the output should be:

7

## sample

3
1 3 1
1 5 1
4 2 1

7