题目描述

王老师养了一只鸡，有一天把它带出来遛。

他们路过一个学校，他的鸡用一种很萌的眼神告诉他它想淘汰学生了。王老师没 ye 办 xiang 法 qu ，只 guo 好 duan 带它进去淘汰，不过为了不被发现，他们只能往下、左、右三个方向走（有联系，吗。。。），走过的教室上如果有学生，他们就会把学生全部淘汰，然后那里的学生不会再有了。这是一个高端的学校，某些点会设有摄像头，当他们走到这些摄像头的时候他们为了不被罚款需要加入一些学生，然后这个摄像头就不再起作用（消失）了。
王老师想到反正都来了，不如多淘汰一点，所以他想知道从第一行任意一个位置开始，一直到最后一行任意一个位置结束，最终他最多能淘汰多少的学生。

输入格式

第 1 行一个整数，N，表示 N × N 的学校。
第 2 ~ n+1 行，每行 N 个整数，Aij 表示第 i 行 j 列上的学生数，如果 Aij 为负数，表示遇到摄像头，必须要加入 -Aij 的学生。相邻整数用一个空格隔开。

输出格式

输出文件一行一个整数，最后淘汰的学生数。

样例输入

3
5 -10 -10
5 -5 20
20 -5 -5

样例输出

45

数据范围

对于 10%的数据：N <= 3
对于 30%的数据：没有摄像头（即全为非负数）
对于所有数据：N <= 50，-10000 <= Aij <= 10000

限制

1s

样例解释

(1,1) → (2,1) → (2,2) → (2,3) → (2,2) → (2,1) → (3,1) → 结束

来源

CWOI新高二专题测试三