Description

Imagine Bessie's surprise as she spotted a leprechaun prancing through the north pasture. Being no one's fool, she charged and captured him with her prehensile hooves.

"One wish, bovine one. That's all I have for cows," he said.

"Riches," Bessie replied dreamily. "The opportunity for riches."

Leprechauns never grant the easiest possible form of a wish. When the smoke from a loud explosion cleared, a shimmering donut spun slowly over the verdant green fields.

"I have made you a torus," the leprechaun cooed. "On that torus is an $N \times N$ matrix ($1 \le N \le 200$) of integers in the range $-1{,}000{,}000..1{,}000{,}000$ that will determine the magnitude of your riches. You must find the contiguous sequence of integers, all in one row, one column, or along one diagonal, that yields the largest sum among all possible sequences on the torus."

Bessie realized that the torus "wraps" the rows, columns, and diagonals of the matrix so that one may choose contiguous elements that wrap around the edges. In other words, the two ends of a row are adjacent, the two ends of a column are adjacent, and even the ends across adjacent rows are adjacent in the diagonal directions. You must choose at least one matrix element.

By way of example, consider the $4 \times 4$ matrix on the left below in which all the elements of one exemplary wrapped diagonal are marked:

The marked diagonal of the right-hand matrix includes two nines (the highest available number) and a six, for a total of $24$. This is the best possible sum for this matrix and uses only three of the four possible elements on that diagonal.

Input Format

• Line 1: A single integer $N$.
• Lines $2..N+1$: Line $i+1$ contains $N$ space-separated integers that compose row $i$ of the matrix.

Output Format

• Line 1: A single integer that is the largest possible sum computable using the rules above.

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

24 

Hint

Translated by ChatGPT 5