Mystery ET

In the year 3890, we ALPCs find that the army of another planet is going to attack the earth, and we have to stop this attack to save our human beings, save the earth.
ALPC2587 has captured an ET, and he starts research this ET. Several days later he draws a conclusion that an ET’s living on the earth depends on a parameter named DR. DR measures the dangerousness of an ET. If an ET has a larger DR, it’s more dangerous. Now ALPCs have to find the maximum value of DR.
But there’s a problem that ET keeps growing: in an experience, first of all, we randomly put a cell of an ET in to box with N*N grids, every grid has a value, which is the value of DR (may be negative) of that grid. Then the cell grows freely and then constructs a creature. The creature’s DR is the total DR of all the girds it captured. In a unit time, the creature can choose one of its cell (grid) to grow to a adjacent grid.
Here’s an example:

ALPC2587 has experienced a lot but he is not clever enough to calculate the maximum DR, and all other ALPCs are busy with other tasks, so he comes to you for help. Please help him to calculate the maximum DR value the creature can gain in an experience.

  There are multiple test cases, please process to the end of file.
  In each the first line contains N (N<=9), the size of the box. Then comes N lines, each has N integers Aij (|Aij| < 32768), indicates the DR value of each grid.

For each case output the maximum DR value the creature can be.

4
2 -1 -1 -1
5 -5 -1 -5
3  2 -1  3
2 -2 -3  2

18

2009 Multi-University Training Contest 17 - Host by NUDT