Bogle: Da wang jiao wo lai xun shan!

You: Can you speak Chinese?

Bogle: Yes~ 大王叫我来巡山，我来收保护费。这山是一个边长为N的直角三角形，如边长为4，下面是一个例子：

1

2 3

4 5 6

7 8 9 10

每一格代表山上的一个洞窟，洞窟里住着别的小妖。我就是去小妖们那里收保护费的。组成三角形的数字代表各小妖能支付得起的保护费。我从山顶一直巡到山脚，然后再回到山顶（山顶为(0, 0)坐标的那个，山脚为(n - 1, n - 1)坐标的那个）。当然啦，反正大王木有来监督，我就随便走走，下山只往下或者往右走，上山除了在山脚是向左上斜着走一步和在山顶下一行是向左上斜着走一步以外，只往上或者往左走。不过，既然收保护费，也不能收少了是吧，我要尽可能地多收。但是嘛，各小妖还是有点脾气的，除了山顶的洞窟，我今天不能路过他们洞窟第二次，不然会被乱棍打死。

所以像上面这座山我的走法就是1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 10 ->(斜向上) 6 -> 5 -> 3 ->(斜向上) 1。其中最后的一次走山顶是回到起点，并不第二次收取他的保护费。

那么，我最多能收多少保护费呢？

This problem has several cases, input until EOF.
The first line of each case is an integer n (4 <= n <= 200), indicates the side length of Right Triangle.
Then input the triangle, each number (Nonnegative) is the money they can offer. No number is bigger than 500.

For each case, output the max money Bogle can receive.