Torus Maximum Subarray

Bessie has been granted a wish by a mischievous leprechaun — but not in the exact way she imagined! You are given an (N \times N) matrix (with (1 \le N \le 200)) of integers in the range ([-10^6,10^6]) arranged on a torus. This means that the rows, columns, and diagonals wrap around: the first and last elements of a row (or column) are considered adjacent, and the same applies for the diagonals.

Your task is to find a contiguous sequence of numbers lying entirely in one row, one column, or along one diagonal (either main diagonal or anti-diagonal) such that their sum is maximized. Note that the sequence may wrap around the boundaries of the matrix due to its toroidal nature, and you must choose at least one element.

More formally, for any valid direction (horizontal, vertical, or diagonal), consider all contiguous segments (of length from 1 up to (N)) in the corresponding circular array. Output the maximum sum obtained.

inputFormat

The input begins with an integer (N) ((1 \le N \le 200)), which is the size of the matrix. Each of the next (N) lines contains (N) integers separated by spaces, representing the rows of the toroidal matrix. All integers are in the range ([-10^6, 10^6]).

outputFormat

Output a single integer — the maximum contiguous subsequence sum that can be obtained from any row, column, main diagonal, or anti-diagonal (taking wrapping into account).

sample

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

10