Maximum Hourglass Sum

You are given a matrix with N rows and M columns. Your task is to find the maximum hourglass sum in the matrix. An hourglass in the matrix is defined as follows:

$$a_{i,j} + a_{i,j+1} + a_{i,j+2} + a_{i+1,j+1} + a_{i+2,j} + a_{i+2,j+1} + a_{i+2,j+2}$$

where 0 \le i \le N-3 and 0 \le j \le M-3. It is guaranteed that N and M are at least 3.

Print the maximum hourglass sum found in the matrix.

inputFormat

The first line contains two space-separated integers N and M, representing the number of rows and columns in the matrix.

The next N lines each contain M space-separated integers denoting the elements of the matrix.

outputFormat

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

6 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