思路：动态规划

首先，观察本题的跳跃方式，有一个共性特点：只会向右跳跃

对于每个位置，我们需要考虑四种跳跃方式：先向右走一步，再向上或向下走两步，或者先向右走两步，再向上或向下走一步。

我们可以定义长度为4的方向数组，来表示这四种跳跃方式

定义$f[i][j]$表示到达$(i,j)$点的最大硬币数量，那么我们可以枚举$(i,j)$是由上述哪一种方式跳跃得到的

题目描述

教练我也想学这个！在一个n*n的正方形训练场上中下标从1-n，每个位置都有一枚硬币，小红从起点出发，跳跃可以先向右走一步，再向上或向下走两步，或者先向右走两步，再向上或向下走一步。但是小红不能跳出训练场，也不能往回跳，不然会遭到教练的严厉表扬。小红左上位置(1,1)上，他想在完成训练获得更多的硬币买快乐水。身为教练的你要帮他吗？

输入描述

第一行输入一个整数n$(3\le n\le 1000)$表示操场大小。接下来n行，每行输入n个整数表示每个位置的权值 $(1\le a_{ij}\le 10^9)$

输出描述

输出一个整数表示答案。

样例

输入

3
1 1 4
5 1 4
1 9 19

输出

14

Limitation

1s, 1024KiB for each test case.