Maximum Hourglass Sum

You are given a square matrix of size n × n consisting of integers. Your task is to find the maximum hourglass sum in the matrix.

An hourglass is defined by a pattern in the matrix as follows:

\(\begin{matrix} a & b & c \\ & d & \\ e & f & g \end{matrix}\)

This means that for any hourglass starting at position \((i, j)\), its sum is computed as:

\(S = a + b + c + d + e + f + g\)

You should consider every possible hourglass in the matrix. Note that since an hourglass requires 3 rows and 3 columns, the top-left corner of any valid hourglass is at a position where both the row index and the column index are less than \(n-2\).

Output the maximum hourglass sum found in the matrix.

inputFormat

The first line contains a single integer n, the size of the matrix. The following n lines each contain n space-separated integers, representing the rows of the matrix.

outputFormat

Output a single integer, the maximum hourglass sum found in the matrix.

## sample

3
1 2 3
4 5 6
7 8 9

35

</p>