Maximum Survival Score

In May 3206, Dr. Liu’s OI team discovered that Earth was invaded by alien beings using a secret multiplicative encryption signal. These aliens had taken over armories, captured many cities and even initiated a K-bomb plan. In response, the team – based at the unique research institute in Jilin Province – captured several aliens. Their research revealed that an alien’s survival on Earth is determined by its survival score, defined as the sum of scores in all grid cells occupied by the alien.

Each experiment begins by placing a single alien cell into a random cell of an N×N square culture container. Each cell of the container is assigned an integer value (which may be positive or negative); a higher number indicates a higher danger level for that cell. After the experiment starts, the alien grows naturally. At each time unit, one cell on the boundary of its body (that is, a cell that shares a common edge with an already occupied cell) may be occupied by the alien. Since the alien is grown cell‐by‐cell in a way that each new cell is adjacent to the current region, the final shape is a connected region in the grid (adjacency by edge only).

After conducting many experiments, the team recorded that at some moment the alien achieved the maximum survival score. Your task is to compute this maximum survival score, that is, the maximum sum of the cell values over any nonempty connected subset of cells in the grid.

Note: Even if all cells have negative values, a connected region consisting of a single cell is valid.

inputFormat

The first line contains an integer N indicating the size of the grid. Each of the following N lines contains N integers separated by spaces. The integer in each cell represents the survival score of that cell. The grid is indexed in 0-based order; the cell in row r and column c corresponds to index r×N+c.

Constraints: It is guaranteed that N is small enough to allow an exhaustive search of the connected regions.

outputFormat

Output a single integer, which is the maximum survival score that can be achieved by any connected region in the grid.

sample

1
5

5