Largest 2x2 Submatrix Sum

Given an (N \times M) matrix of integers, your task is to find the maximum sum of any 2x2 submatrix. A 2x2 submatrix consists of two consecutive rows and two consecutive columns. Formally, if (A) is the given matrix, you need to compute the maximum of (A_{i,j} + A_{i,j+1} + A_{i+1,j} + A_{i+1,j+1}) for all valid (i) and (j). This is a common problem in competitive programming that tests your ability to process multi-dimensional arrays efficiently.

inputFormat

The first line contains two integers (N) and (M), representing the number of rows and columns respectively. The following (N) lines each contain (M) space-separated integers that represent the elements of the matrix. Input should be read from stdin.

outputFormat

Output a single integer which is the largest sum among all 2x2 submatrices found in the given matrix. Output should be written to stdout.## sample

3 3
1 2 3
4 5 6
7 8 9

28