Minimum Delivery Cost

A courier company needs to optimize its delivery schedule within a city organized in a grid layout. The city is represented as an \(N \times N\) grid where each cell has an associated time cost. The courier starts at the top-left cell (index \(0,0\)) and must reach the bottom-right cell (index \(N-1,N-1\)) while only moving either right or down at each step.

Your task is to determine the minimum total time cost required to traverse from the starting cell to the destination cell. The optimal path minimizes the sum of the time costs of the cells visited.

Input Constraints:

• \(1 \leq N \leq 10^3\) (for example)
• Time costs are non-negative integers.

Example:

For the grid:

1 3 1
1 5 1
4 2 1

the minimum delivery cost is \(7\): 1 \(\rightarrow\) 3 \(\rightarrow\) 1 \(\rightarrow\) 1 \(\rightarrow\) 1.

inputFormat

The input is given via stdin. The first line contains an integer \(N\) representing the size of the grid. The next \(N\) lines each contain \(N\) space-separated integers, representing the time cost for each cell in the grid.

Example Input:

3
1 3 1
1 5 1
4 2 1

outputFormat

The output should be printed to stdout as a single integer, which is the minimum delivery cost (the minimum sum of time costs) from the top-left cell to the bottom-right cell.

Example Output:

7

## sample

3
1 3 1
1 5 1
4 2 1

7