福里克和鲁比克参加接力赛。比赛将在一个边长为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)。示例图: