Maximum Hourglass Sum

You are given an n x n grid of integers. Your task is to find the maximum hourglass sum in the grid. An hourglass in the grid is defined by the following pattern:

$$ \begin{array}{ccc} a & b & c \\ & d & \\ e & f & g \end{array} $$

This means that for any position (i, j) in the grid such that the hourglass fits inside the grid (i.e. with 0 \leq i \leq n-3 and 0 \leq j \leq n-3), the hourglass sum is calculated as:

$$S = grid[i][j] + grid[i][j+1] + grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2]$$

Your program should find and output the maximum hourglass sum among all possible hourglasses in the grid.

inputFormat

Input Format:

• The first line contains a single integer n (where n ≥ 3), the dimension of the grid.
• The next n lines each contain n space-separated integers, representing the rows of the grid.

outputFormat

Output Format:

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

## sample

4
1 1 1 0
0 1 0 0
1 1 1 0
0 0 0 0

7