← 返回题目列表

Codeforces · 1765/K

K. 环面路径

中文机器翻译题面 查看原题

为您提供一个包含 $$$n$$$ 行和 $$$n$$$ 列的方形网格,其中每个单元格中都写入一个非负整数。有一个芯片最初放置在左上角的单元格(坐标为 $$$(1, 1)$$$ 的单元格)。您需要将芯片移动到右下角的单元格(坐标为 $$$(n, n)$$$ 的单元格)。

您只需一步即可将芯片移动到相邻单元格,但是:

1. 您只能向右或向下移动。换句话说,如果当前单元格是 $$$(x, y)$$$,您可以移动到 $$$(x, y + 1)$$$ 或 $$$(x + 1, y)$$$。有两种特殊情况:如果芯片位于最后一列(单元格 $$$(x, n)$$$)并且您向右移动,您将传送到第一列(单元格 $$$(x, 1)$$$); 如果筹码位于最后一行(单元格 $$$(n, y)$$$)并且您向下移动,您将传送到第一行(单元格 $$$(1, y)$$$)。
2. 您不能两次访问同一个单元格。起始单元格从头开始计算访问次数(因此您无法再次输入),并且一旦访问结束单元格就无法离开它。

您的总分计算为您访问过的所有单元格中的数字总和。您能获得的最高分数是多少?

输入

第一行包含单个整数 $$$n$$$ ($$$2 \le n \le 200$$$) — 网格中的行数和列数。

接下来的 $$$n$$$ 行包含网格每行的描述。第 $$$i$$$ 行包含 $$$n$$$ 整数 $$$a_{i, 1}, a_{i, 2}, \dots, a_{i, n}$$$ ($$$0 \le a_{i, j} \le 10^9$$$),其中 $$$a_{i, j}$$$ 是写入单元格 $$$(i, j)$$$ 中的数字。

输出

打印一个整数 - 您可以获得的最高分数。

示例

输入 #1

2
1 2
3 4

输出 #1

8

输入 #2

3
10 10 10
10 0 10
10 10 10

输出 #2

80