题目内容

在一个 $n \times n$ 的宝石矿区中，每个格子中都藏有价值不菲的宝石。一台机器人从左上角的 $(1,1)$ 格子出发，目的地是矿区中的任意可达格子。

机器人的移动方式受到特殊限制：它只能向右移动，并且每次只能选择以下两种跳跃方式之一：

• 方式一：先向右移动 $1$ 列，再向上或向下移动 $2$ 行。
• 方式二：先向右移动 $2$ 列，再向上或向下移动 $1$ 行。

机器人在跳跃过程中不能跳出矿区的边界，并且由于只能向右移动，每次跳跃后的列编号必须严格大于跳跃前的列编号。到达一个格子后，机器人会自动收集该格子内的所有宝石。

给定矿区每个格子的宝石价值，你的任务是计算出从 $(1,1)$ 出发，在遵守移动规则的前提下，机器人能够收集到的宝石总价值的最大值。

网格的边长 $n$ 满足 $3 \le n \le 1000$，每个格子内的宝石价值均为不超过 $10^9$ 的正整数。

输入描述

第一行包含一个整数 $n$，表示矿区的边长。 接下来的 $n$ 行，每行包含 $n$ 个整数，依次表示矿区中对应位置的宝石价值。

输出描述

输出一个整数，表示机器人能够收集到的最大宝石总价值。

样例1

输入

3
10 1 1
1 1 20
1 30 1

输出

40

说明

从起点 $(1,1)$ 价值为 10 开始。可以选择方式一：向右 1 列、向下 2 行到达 $(3,2)$，获得价值 30，总价值达到 40。 也可选择方式二：向右 2 列、向上 1 行到达 $(2,3)$，获得价值 20，总价值为 30。 由于后续无合法移动，最大总价值为 40。

样例2

输入

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

输出

27

说明

从 $(1,1)$（价值 1）出发，考虑所有路径：

• 路径1：$(1,1) \to (3,2)$ (10) $\to (4,4)$ (16)，总价值 $1+10+16=27$。
• 路径2：$(1,1) \to (3,2)$ (10) $\to (1,3)$ (3) $\to (3,4)$ (12)，总价值 $1+10+3+12=26$。
• 路径3：$(1,1) \to (2,3)$ (7) $\to (4,4)$ (16)，总价值 $1+7+16=24$。
• 路径4：$(1,1) \to (3,2)$ (10) $\to (2,4)$ (8)，总价值 $19$。 比较可得最大值为 27。

样例3

输入

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出

4

说明

所有宝石价值均为 1，因此最大化总价值等价于寻找最长可达路径。 从 $(1,1)$ 出发，最长路径为 $(1,1) \to (3,2) \to (1,3) \to (3,4)$，沿途共收集 4 个格子的宝石，总价值为 4。 无法找到更长的路径，故输出 4。