Background

Special for beginners, ^_^

Description

有一片边长为 n 的正方形“颠倒”海域。在颠倒海中，船只能直走，不能拐弯、变向。从(x,y)向左、右、上、下走一格分别会到达(x,(y-2+n) mod n +1)、(x,y mod n +1)、((x-2+n)mod n+1,y)、(x mod n+1,y)。也可以斜着走（左上，右上，左下，右下）。向左上走就相当于先向左走再向上走，但是只能判定左上方那格的财宝。

海里每一格都有财宝（可能为负）。他必须选择财宝最多的航线航行一次才能通过颠倒海。起始点任意选。(航行期间任意时刻的最大值都有效！)

Format

Input

第一行一个整数表示颠倒海域的边长 n。

以下是一个 n*n 的矩阵表示每格的财宝。

Output

输出文件仅有一行表示财宝总数。

Samples

4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2

24

Limitation

20%的数据,1<=N<=20。

100%的数据，1<=N<=100。

对于样例的解释：(3,4)->(4,3)->(1,2)