题目描述

给你一个 $n * n$ 的整数方阵 matrix 。你可以执行以下操作 任意次 ：

选择 matrix 中 相邻 两个元素，并将它们都 乘以 $-1$。 如果两个元素有 公共边 ，那么它们就是 相邻 的。

你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。

输入格式

第一行一个整数$n(2 <= n <= 250)$

第$2$到$n+1$行$n$每行$n$个数

输出格式

输出最大和

样例 #1

样例输入 #1

3
1 2 3 
-1 -2 -3 
1 2 3

样例输出 #1

16

样例 #2

样例输入 #2

2
1 -1
-1 1

样例输出 #2

4

提示

样例1：

1 2 3

-1 -2 -3 变成

1 2 3

1 2 3

-1 2 3

1 2 3

样例2：

1 -1

-1 1

变成

-1 1

-1 1

变成

1 1

1 1

数据范围

$n == matrix.length == matrix[i].length$

$2 <= n <= 250$

$-10^5 <= matrix[i][j] <= 10^5$