摘樱桃

题目描述

樱桃谷的管家想把谷口的樱桃运到谷底的祭坛。整片山谷被划成 $n\times n$ 的格子，管家先推着空车从入口 $(1,1)$ 走到祭坛 $(n,n)$，再沿着另一条路返回入口。规定只能向下或向右移动，返回时同样只能向上或向左（等价于两名管家同时从入口出发、各走一趟到祭坛）。

格子中：

• $0$ 表示空地；
• $1$ 表示有一筐樱桃；
• $-1$ 表示巨石堵路，无法进入。

每筐樱桃只能被搬走一次（两趟路线都经过同一格时，该格樱桃至多算一份）。求管家能够带回入口的樱桃最大数量；若无法完成往返，则输出 $0$。

输入格式

第一行包含一个整数 $n$，表示山谷边长。

接下来 $n$ 行，每行包含 $n$ 个整数，描述整张网格。

输出格式

输出一个整数，表示最多可收集的樱桃数量；若任务无法完成，输出 $0$。

输入输出样例 #1

输入 #1

5
0 1 -1 0 0
1 0 -1 1 1
0 1 0 1 0
1 0 0 0 1
0 -1 1 1 0

输出 #1

6

数据范围

对于 $100\%$ 的数据，$1 \le n \le 50$，网格元素为 $-1,0,1$。入口与祭坛所在格子不会被巨石堵住。EOF