小H来到一块西瓜地，发现这块西瓜地只能往下、左、右三个方向走，走过的点上如果有西瓜，小H就会全部摘走，然后那里的西瓜就木有了。农场主怕小H把西瓜都摘完，在某些点设置了小仓库，当你走到这些小仓库的时候，你必须用西瓜把仓库塞满，现在小H从第一行任意一个位置开始，一直到最后一行任意一个位置结束，最终小H最多能得到多少的西瓜。

输入 第 1 行一个整数，N，表示 N×N 的西瓜地 第 2 ~ n+1 行，每行 N 个整数，Aij 表示第 i 行 j 列上的西瓜数，如果 Aij 为负数，表示遇到小仓库，仓库需要你放 |Aij| 的西瓜。相邻整数用一个空格隔开。

输出 输出文件一行一个整数，最后获得的西瓜数。

样例输入 3 5 0 7 1 1 3 -9 0 -9

样例输出 17

提示 对于所有数据：N,M<=50，-10000<= Aij <=10000 解释：(1,1) (1,2) (1,3) (2,3) (2,2) (2,1) (2,2) (3,2) 结束 为方便你理解再给你一组样例

样例输入

3

4 -10 -10

4 -5 10

10 -5 -5

样例输出

23

解释：(1,1) (2,1) (2,2) (2,3)(2,2) (2,1) (3,1) 结束