呆头呆脑的小明听信他人蛊惑，拿着藏宝图，站在 正方形 迷宫口，别人告诉他这个正方形迷宫有很多节点，每个节点都有相应的奖励，且已经在地图上标出来，而小明每次只能往迷宫 下方 节点或 右下方 前进，于是小明又一次听信了他人的话，不仅如此，他还想知道怎样才能在到达迷宫对边时使奖励最大化？
注意
迷宫口即正方形的左上角，小明亦从此出发
输入格式
第一行为整数n，表示迷宫的边长
一下n+1至2n+1行为地图

输入样例

3
1 0 0
1 0 0
1 0 0

输出样例

3

数据规模

目前为止 \(n \leq 30\)