The Leprechaun

Bessie spotted a leprechaun prancing through the north pasture and, being no one's fool, charged and captured him with her nimble hooves.

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

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

Leprechauns never grant the easiest form of their captor's wish. As the smoke from a loud explosion cleared, a shimmering donut spun slowly over the verdant fields.

"I have made you a torus," the leprechaun cooed. "On that torus sits an $N \times N$ matrix of integers ($1 \le N \le 200$), each in the range $-1{,}000{,}000$ to $1{,}000{,}000$, that will determine the magnitude of your riches. You must find the contiguous run of integers, lying entirely within one row, one column, or one diagonal, that yields the largest sum."

Because the matrix lies on a torus (a donut), every row, column, and diagonal wraps around: its two ends are joined into a loop. So when you pick a run of consecutive elements along a line, you may continue past one end and "wrap around" to the other end.

• Row: the elements of a row wrap left/right.
• Column: the elements of a column wrap top/bottom.
• Diagonal: there are two directions (the ↘ direction and the ↙ direction), and each diagonal also wraps. On a torus there are exactly $N$ diagonals in each direction, and each diagonal passes through $N$ distinct elements.

Among all such runs (a run of consecutive elements along a single row, column, or diagonal, containing at least one element), determine the largest achievable sum. A run never uses the same element twice, so it contains at most $N$ elements.

For example, in the $4 \times 4$ matrix below, consider one ↙-direction diagonal (its starred elements).

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

This diagonal loops through $(0,1)=6$, $(1,0)=-3$, $(2,3)=9$, $(3,2)=9$ (coordinates are 0-based (row, column)). Skipping $-3$ and wrapping around to take $9$, $9$, $6$ gives $9+9+6=24$, the best sum possible for this matrix.

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

• A single integer: the largest sum obtainable under the rules above.