Description

Ciel有一个$N*N$的矩阵，每个格子里都有一个整数。 $N$是一个奇数，设$X = (N+1)/2$。Ciel每次都可以做这样的一次操作：他从矩阵选出一个$X*X$的子矩阵，并将这个子矩阵中的所有整数都乘以$-1$。 现在问你经过一些操作之后，矩阵中所有数的和$最大$可以为多少。

Format

Input

第一行为一个正整数$N$。 接下来$N$行每行有$N$个整数，表示初始矩阵中的数字。每个数的绝对值不超过$1000$。$（1 < = N < = 33，且N为奇数。）$

Output

输出一个整数，表示操作后矩阵中所有数之和的最大值。

Samples

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

9