Maximum Gold Collection

You are given an n×n grid where each cell contains a non-negative integer representing the amount of gold at that position. A player starts at the top-left cell (0, 0) and must travel to the bottom-right cell (n-1, n-1). At each step, the player may only move either right or down.

Your task is to determine the maximum amount of gold that can be collected when the player reaches the destination. The problem can be solved using dynamic programming. Define dp(i, j) as the maximum gold that can be collected when arriving at cell (i, j). The recurrence relation is given by:

$$dp(i,j) = A[i][j] + \max\bigg\{ \begin{array}{l} dp(i-1, j) \quad \text{(if } i > 0 \text{)} \\ dp(i, j-1) \quad \text{(if } j > 0 \text{)} \end{array} $$

with the initial condition dp(0, 0) = A[0][0]. Output the maximum gold collected at cell (n-1, n-1).

inputFormat

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

• The first line contains an integer n (1 ≤ n ≤ 1000), the size of the grid.
• The following n lines each contain n space-separated integers indicating the value of each cell in the grid.

outputFormat

Output a single integer representing the maximum gold that can be collected from the top-left to the bottom-right cell. The result should be printed to stdout.

## sample

3
1 3 1
1 5 1
4 2 1

12