Our airplane can be represented as a square grid of size ` N × N`. Each cell of the grid contains a seat, occupied by a person with some specific uselessness (represented by an integer between -1000 and +1000). A snake enters the airplane at some position. As the snake moves through the grid, he eats each person whose seat it reaches.

The snake has three move commands:

- D
- Move down one or more cells.
- L
- Move left one or more cells.
- R
- Move right one or more cells.

The snake may begin with any of these commands, and must use them in the order **LD RD LD RD LD RD….** It may stop at any time.

Here are some examples of correct snake paths (start position is #):

`.#>>v.`

....v.

<<<<<.

v.....

v.....

......`..#>v.`

.v<<<.

.>>>>v

.....v

.<<<<<

......`......`

..#...

..v...

..>>v.

....v.

...<<.`......`

......

......

..#...

......

......

Since he's had enough of these motherfucking snakes on this motherfucking plane, Samuel L. Jackson wants to find a suitable path for the snake, such that the total uselessness of the people who are eaten is maximum.

# Input

The first line of input contains integer ` N`.

Each of the following

`lines contains a sequence of`

**N**`integers each.`

**N**# Output

The output should contain a single value: the maximum total uselessness that the snake can eat.

# Constraints

- N ≤ 1000
- -1000 ≤ matrix values ≤ 1000
- The snake always eats the value on the starting position.

# Example

Input | Output |
---|---|

51 1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 | 15 |

First, let's take a look at the limits: `N ≤ 1000`. This suggests the complexity `O(N^2)`. The problem can be solved by DP and the solution should be pretty straight forward.

To make a good solution we'll solve a simpler problem at first. Let's assume D means just one step down. This particular problem can be solved by the folowing DP:

`dp[dir][i][j]` = the largest sum of a sequence that ends in position `(i, j)`, considering that the snake is coming from direction `dir` (`0` for left or `1` for right).

Returning to the initial problem, the DP seems simpler now: `dp[dir][des][i][j]` = the largest sum of a sequence that ends in position `(i, j)`, considering that the snake is coming from direction `dir` (`0` for left, `1` for right) and is descending or not (`des = 0/1 ). `

The following cases must be analyzed:

- The snake goes down.
- The snake continues to move to the left or to the right.
- The snake stops descending and swaps the direction.

Time complexity: `O(N^2)`.