https://oj.czos.cn/p/2436

现在有一个 N×N 的矩阵，在这个矩阵的每个格子都有若干能量水晶。 现在，小明从这个矩阵的左边出发，目的地是这个矩阵的右边。 当他走到一个格子时，他就能获得这个格子的能量水晶； 小明最开始会从左边的路边走到这个矩阵的第一列的任意一个格子里。当他处于这个矩阵的最后一列的时候，他必须往右走一步离开这个矩阵。 当他处于这个矩阵里时，每次只能从一个格子往右上方走一步或者往右下方走一步； 但是当他处于第一行时，就只能往右下方走；同理，当他处于第 N 行时，就只能往右上方走。 现在要知道当他离开矩阵时获得的能量水晶最多能有多少。

样例

输入 3

1 2 3

3 2 1

2 3 1

输出 7