Problem G
Lopsided Lineup

Unbalanced scales
(from WikiMedia Commons)

Together with your coworker, Sergey, you are organizing the exciting Billiards and Pool Competition for your coworkers in your small company. However, communication has not been great between you two. You are not sure you and Sergey think alike, but as far as you are concerned, this would be a great opportunity to do some team building. The actual prizes are meaningless, but there is possibly a lot to be gained from this in team bonding. You want to maximise result.

You start reading some pseudo-scientific books on team management, and after some research, you conclude that there are two good ways of team bonding: people feel more connected after either a triumphant victory or a crushing defeat. This gives you a great idea: if you divide your coworkers into two groups that are as far apart in skill level as possible, both teams will experience improved bonding! You therefore think it is optimal to try to make the teams as unbalanced as possible. Make sure, however, that the teams are of equal size.

With a bit of work you come up with a nice model for the strength of a team. You think team strength is mainly determined by how well two players play together, whether they encourage one another and complement each other’s weaknesses. Whenever two players $i$ and $j$ are in the same team, they increase the team score by an integer $c_{i,j}$. The total score of a team is thus equal to the sum of $c_{i,j}$, over all unordered pairs of players $i$ and $j$ in the team.

Input

The input consists of:

• One line with an even integer $n$ ($2\leq n\leq 1000$), the total number of players.

• $n$ lines, the $i$th of which contains $n$ integers $c_{i,1}, c_{i,2}, \dots , c_{i, n}$ ($-10^6\leq c_{i,j} \leq 10^6$).

  For any $i$ and $j$, it is guaranteed that $c_{i,i} = 0$ and $c_{i,j} = c_{j,i}$.

Output

Output the maximum possible difference in strength between two teams of equal size.

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

0

4
0 1 2 2
1 0 8 -3
2 8 0 5
2 -3 5 0

6