Maximum Path Sum in a Grid

You are given an \(N \times N\) grid filled with integers between 1 and 9. Starting from the top-left corner, you need to reach the bottom-right corner by moving only to the right or down. At each cell you collect the number written there, and your goal is to maximize the total sum collected on your path.

Constraints: \(1 \leq N \leq 50\). Each integer in the grid is between 1 and 9.

For example, given the grid below:

1 2 3
4 5 6
7 8 9

The maximum sum path is 1 \(\to\) 4 \(\to\) 7 \(\to\) 8 \(\to\) 9 with a sum of 29.

inputFormat

The first line contains a single integer \(N\), which is the size of the grid. The following \(N\) lines each contain \(N\) space-separated integers, representing the grid rows.

outputFormat

Output a single integer: the maximum sum achievable by moving from the top-left corner to the bottom-right corner, moving only right or down.

## sample

3
1 2 3
4 5 6
7 8 9

29

</p>