Maximum Sum Clues

You are given an n x n square grid of integers. The grid is provided in order from the bottom row to the top row. Your task is to compute the maximum sum path from the bottom-left corner to the top-right corner.

You can only move in two directions: up (i.e. to the cell directly above) or right (i.e. to the cell directly to the right). Formally, if the path is represented by a sequence of coordinates \((i,j)\) where the bottom-left corner is \((0,0)\) and the top-right corner is \((n-1, n-1)\), then you need to maximize the sum

\(\sum_{(i,j) \in path} grid[i][j]\)

It is guaranteed that there is at least one valid path. Output the maximum sum that can be obtained.

inputFormat

The first line contains a single integer (n) representing the size of the grid. Each of the next (n) lines contains (n) space-separated integers representing a row of the grid, provided from bottom (first line) to top (last line).

outputFormat

Output a single integer — the maximum sum that can be collected from the bottom-left corner to the top-right corner by moving only up or right.## sample

3
1 2 3
4 5 6
7 8 9

29