← 返回题目列表

Codeforces · 321/D

D. Ciel 和 Flipboard

中文机器翻译题面 查看原题

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 子板上。那么所有的数字都会变成正数。