Maximum Hourglass Sum

Given an n × n grid of integers, your task is to find the hourglass with the maximum sum. An hourglass is defined as a subset of values with indices forming the following pattern:

\( 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] \)

You are required to compute this maximum hourglass sum. Note that the grid will always be of size n × n, and an hourglass can only be formed in a grid with n >= 3.

inputFormat

The input is read from standard input (stdin). The first line contains an integer n representing the size of the grid. This is followed by n lines, each containing n space-separated integers representing the rows of the grid.

outputFormat

Print to standard output (stdout) a single integer, the maximum hourglass sum found in the grid.## sample

6
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0

19