题目描述

现在有一个 $N \times N$ 的矩阵，在这个矩阵的每个格子都有若干能量水晶。

现在，小明从这个矩阵的左边出发，目的地是这个矩阵的右边。

当他走到一个格子时，他就能获得这个格子的能量水晶；

小明最开始会从左边的路边走到这个矩阵的第一列的任意一个格子里。当他处于这个矩阵的最后一列的时候，他必须往右走一步离开这个矩阵。

当他处于这个矩阵里时，每次只能从一个格子往右上方走一步或者往右下方走一步；但是当他处于第一行时，就只能往右下方走；同理，当他处于第 $N$ 行时，就只能往右上方走。

现在要知道当他离开矩阵时获得的能量水晶最多能有多少。

输入

第一行为一个正整数 $N$ ；

接下来 $N$ 行，每行 $N$ 个数，空格隔开，描述这个 $N \times N$ 的矩阵，每一个数代表该格里面水晶的数目。

输出

一个数，表示小明离开矩阵时获得的能量水晶最多能有多少。

样例

3
1 2 3
3 2 1
2 3 1

7

说明

【样例解释】

【数据范围】

$20\%$ 的数据满足：每个格子里的能量水晶相等；

$50\%$ 的数据满足： $1 ≤ N ≤ 10$ ；

$100\%$ 的数据满足： $1 ≤ N ≤ 1000$ ，每个格子里的能量水晶均不超过 $10$ 个。