E. Cupcake Collecting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice has been teleported into Cupcakeland! Before returning home, she wants to make the most out of her stay by collecting as many cupcakes as possible.

Cupcakeland is represented by a $$$N$$$ x $$$N$$$ grid ($$$1 \leq N \leq 1000$$$), and Alice starts out at the top left corner of the grid. The exit to Cupcakeland is located at the bottom right corner of the grid.

Each remaining square in the grid either contains a $$$-1$$$, denoting an impenetrable tree, or an integer $$$k$$$ ($$$0 \leq k \leq 1000$$$), denoting the number of cupcakes in that square. It is guaranteed that the start and exit squares have 0 cupcakes.

As Alice makes her way to the exit, she will gather all cupcakes that she encounters. Additionally, since she doesn't want to get lost in Cupcakeland, she will only move either downwards or rightwards (towards the exit). Remember that she cannot pass through cells with $$$-1$$$ since they are impenetrable. Please help Alice figure out how many cupcakes she can collect if she chooses the optimal route. If it is impossible for Alice to make it to the exit, please output $$$-1$$$.

Input

The first line of the input contains an integer $$$N$$$.

The next $$$N$$$ lines of the input contain $$$N$$$ space-separated integers, representing the grid.

Output

Please output a single integer, denoting the maximum number of cupcakes Alice can collect on her way out. If it is impossible for her to reach the exit, please output $$$-1$$$.

Examples
Input
4
0 2 3 9
15 0 4 5
0 -1 -1 0
9 0 1 0
Output
25
Input
4
0 2 3 9
15 0 4 5
0 -1 -1 -1
9 -1 1 0
Output
-1