Problem 1 : Grid game

You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.

Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path.

Input format

The first line of the input contains one integer N, the number of rows and columns in the grid. Lines 2 to N+1 describe the N rows of the grid. Each of these N lines of input consists of N space separated integers, corresponding to the numbers in one row.

Notes

In all cases, N ≤ 2000. Each number in the grid is guaranteed to be less than 1000.

Output format

Your output should be a single line consisting of one integer, the sum of the values on the path of maximum weight.

```4
12 -16 10 -12
-16 13 -14 7
7 -4 16 -15
-7 16 -9 8
```

Sample Output

```32
```

Copyright (c) IARCS 2003-2020;   Last Updated: 01 Dec 2009