Fox Ciel 有一块 n 行 n 列的棋盘,每个单元格中有一个整数。
已知n是奇数,所以我们引入$$x = \frac{n+1}{2}$$。 Fox Ciel可以多次执行以下操作:她选择一个大小为x行x列的子板,然后其中的所有数字将乘以-1。
返回她通过这些操作可以获得的棋盘中数字的最大和。
输入
第一行包含一个整数 n,(1 ≤ n ≤ 33,n 为奇数)——棋盘的大小。
接下来的 n 行中的每一行都包含 n 个整数——棋盘上的数字。每个数字的绝对值不超过 1000。
输出
输出单个整数:棋盘中可以完成的最大数字之和。
示例
输入 #1
3 -1 -1 1 -1 1 -1 1 -1 -1
输出 #1
9
输入 #2
5 -2 0 0 0 -2 0 -2 0 -2 0 0 0 -2 0 0 0 -2 0 -2 0 -2 0 0 0 -2
输出 #2
18
注意
在第一个测试中,我们可以应用此操作两次:首先在左上角的 2 × 2 子板上,然后在右下角的 2 × 2 子板上。那么所有的数字都会变成正数。