Description

In May 3206, Dr. Liu, who was studying the ET major, and his OI team discovered that Earth had been invaded by alien “bio-people.” These bio-people used a top-secret multiplicative encrypted telegraph, seized armories with a vast number of weapons, captured many cities, and even launched the K-bomb plan.

Dr. Liu’s OI team decided to leverage their research institute (due to the unique geographical advantages of Jilin, this institute exists only in Jilin worldwide) to subdue these alien bio-people. They managed to capture several alien bio-people, and after research, they found that their survival on Earth depends on one parameter: the survival value. What they aimed to do was to find the maximum value of this parameter. Thus, they began studying the growth of these alien bio-people.

Before each experiment, they randomly place the cell of an alien bio-person into a cell of an $N\times N$ square culture container, and label each cell of the container with a value, which is the survival value of the organism in that cell (can be positive or negative, and a larger value indicates greater danger). The survival value of the entire organism is the sum of the survival values of all the cells it occupies. After the experiment begins, the organism grows naturally. At each unit of time, it chooses a part of its body (some cell) and randomly grows into an empty cell that shares a common edge with it. For example, in one experiment, the organism initially occupies only one cell, and then starts growing:

Dr. Liu’s OI team conducted a large number of experiments and recorded and analyzed the testdata. Assuming the number of experiments is sufficient, ask: at some moment during the experiment, what is the maximum survival value the organism can achieve?

In September 3206, the alien bio-people who attempted to destroy Earth were finally subdued by Dr. Liu’s OI team.

Input Format

The first line contains a positive integer $N$, representing the side length of the experimental container.

The next $N$ lines each contain $N$ space-separated integers, representing the survival value of the alien bio-person in each cell.

Output Format

Output one line, the maximum survival value achieved by the organism during the experiment.

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

18

Hint

For 40% of the testdata, $N \le 6$.

For 100% of the testdata, $N \le 9$.

For all testdata, the absolute value of the survival value in each cell does not exceed $32767$.

Translated by ChatGPT 5