Maximum Hourglass Sum

You are given an n x m grid of integers, where n and m are both at least 3. An hourglass in the grid is defined by the following pattern:

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

Your task is to compute the maximum hourglass sum, which is defined as the sum of the values in the cells that form an hourglass. In other words, if you pick an hourglass with elements $$ a, b, c, d, e, f, g, $$ its sum is a + b + c + d + e + f + g, and you need to determine the maximum such sum from all possible hourglasses in the grid.

You can assume that the input grid will always have at least 3 rows and 3 columns so that at least one valid hourglass exists.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two space-separated integers n and m (with n, m ≥ 3), representing the number of rows and columns in the grid.
• The next n lines each contain m space-separated integers, representing the elements of the grid.

outputFormat

Print a single integer to stdout — the maximum hourglass sum found in the grid.

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

13