20005. 矩陣總和最大值

Task Description

有一個大小為 n*n 的矩陣，你可以對它做以下一種操作不限次數：

【任意選兩個矩陣中相鄰的位置（直的或是橫的相鄰元素），並將兩數值各自乘上-1。】

請你計算出能夠取得的矩陣總和最大值。

範例：

左方為原始矩陣，先對上面兩元素各自乘上-1，接著對左方兩元素乘上-1即可使所有數值皆為正，取得最大值。

1
2
1  -1      -1 1      1 1
-1  1      -1 1      1 1

Hint

每一次操作皆同時對2個元素，因此若原始矩陣中負數的數量為奇數的話，不管做幾次都至少會有1個負數殘留。

Input Format

第一行為矩陣邊長n，接下來會有n行n個數值代表矩陣內容。

（2 <= n <= 10、-100 <= matrix[i][j] <= 100）

Output Format

輸出一數值代表矩陣總和最大值。

Sample Input

1
2
3
4
3
3 -5 2
-1 4 -3
6 -6 -6

Sample Output

1
34