### Zonal Computing Olympiad 2009, 20 Dec 2008

### 10:00 am-1:00 pm IST

### 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.

### Sample Input

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

### Sample Output

32