← 返回题目列表

Codeforces · 213/C

C. 接力赛

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

福里克和鲁比克参加接力赛。比赛将在一个边长为n米的大广场上进行。给定的正方形被分成 n × n 个单元(表示为单位正方形),每个单元都有一些数字。

比赛开始时,Furik 站在坐标为 (1, 1) 的单元格中,而 Rubik 则站在坐标为 (n, n) 的单元格中。开始后Furik就向Rubik跑去,另外,如果Furik站在坐标为(i,j)的单元格,那么他可以移动到(i+1,j)或(i,j+1)的单元格。当Furik到达Rubik后,Rubik开始从坐标为(n, n)的单元格跑到坐标为(1, 1)的单元格。如果魔方站在 (i, j) 格中,那么他可以移动到 (i - 1, j) 或 (i, j - 1) 格。福里克和鲁比克都不允许超出场地范围;如果选手超出界限,他将被取消比赛资格。

为了赢得比赛,Furik 和 Rubik 必须获得尽可能多的积分。点数是 Furik 和 Rubik 访问过的单元格中的数字之和。每个单元格在总和中仅计数一次。

打印出 Furik 和 Rubik 在接力赛中可以获得的最大分数。

输入

第一行包含一个整数 (1 ≤ n ≤ 300)。接下来的 n 行每行包含 n 个整数:第 i 行的第 j 个数字 ai, j (- 1000 ≤ ai, j ≤ 1000) 是写入坐标为 (i, j) 的单元格中的数字。

输出

在一行上打印一个数字——问题的答案。

示例

输入 #1

1
5

输出 #1

5

输入 #2

2
11 14
16 12

输出 #2

53

输入 #3

3
25 16 25
12 18 19
11 13 8

输出 #3

136

注意

对第二个样本的评论:Furik 的盈利路径为:(1, 1)、(1, 2)、(2, 2),Rubik 的盈利路径为:(2, 2)、(2, 1)、(1, 1)。

对第三个样本的评论:Furik 的最佳路径是:(1, 1)、(1, 2)、(1, 3)、(2, 3)、(3, 3),而 Rubik 的最佳路径是:(3, 3)、(3, 2)、(2, 2)、(2, 1)、(1, 1)。示例图: