Description

Ciel有一个n行n列的板子，每个格子上有一个数字。 已知n是一个奇数，不妨设x=(n+1)/2。Ciel可以选择一个x行x列的子矩阵，并将其中的所有元素乘-1。他可以使用这个操作任意多次。 Ciel的目标是最大化板子上的数字和。

Input Format

第一行一个正整数n(1<=n<=33,n是奇数)表示板子大小。 接下来n行每行n个数代表板子上的数，每个数字的绝对值不超过1000。

Output Format

输出可能达到的最大数字和。

Sample

【样例输入】

3
-1 -1 1
-1 1 -1
1 -1 -1

【样例输出】

9

Hint

对于30%的数据n<=7。 对于70%的数据n<=19。 对于100%的数据n<=33。