提示: 欢迎访问OurACM平台。
Problem 2234 牧场物语

Accept: 238    Submit: 1247
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

小茗同学正在玩牧场物语。该游戏的地图可看成一个边长为n的正方形。

小茗同学突然心血来潮要去砍树,然而,斧头在小茗的右下方。

小茗是个讲究效率的人,所以他会以最短路程走到右下角,然后再返回到左上角。并且在路上都会捡到/踩到一些物品,比如说花朵,钱和大便等。

物品只能被取最多一次。位于某个格子时,如果格子上还有物品,就一定要取走。起点和终点上也可能有物品。

每种物品我们将为其定义一个价值,当然往返之后我们取得的物品的价值和越大越好。但是小茗同学正在认真地玩游戏,请你计算出最大的价值和。

Input

多组数据(<=10),处理到EOF。

第一行输入正整数N(N≤100),表示正方形的大小。

接下来共N行,每行N个整数Ai,j(|Ai,j|≤10^9),表示相应对应位置上物品的价值。值为0表示没有物品。

Output

每组数据输出一个整数,表示最大价值和。

Sample Input

2 11 14 16 12

Sample Output

53

Source

福州大学第十三届程序设计竞赛

Submit  Back  Status  Discuss