棋盘游戏

时间限制:10s      空间限制:512MB

题目描述

在一个游戏中,给定一个 n  n 的正方形棋盘,每个格子内有一个整数。保证 n 为奇数。令
x = (n+1)/2 。你可以进行下述操作任意次:每次选择一个 x  x 的子棋盘,将其中所有数乘上-1。
求经过一系列操作后棋盘上所有数之和的最大值。


输入格式

第一行为整数 n。接下来 n 行每行包括 n 个整数,描述棋盘初始时每一个格子内的整数。


输出格式

经过任意次操作后棋盘上所有数之和的最大值。


样例输入

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

样例输出

9

提示

n <= 33
-1000 <= 棋盘内的数字 <= 1000


题目来源

By 佚名提供