Maximum Subrectangle Sum

You are given a matrix of integers with dimensions N by M. Your task is to find the maximum sum over all possible subrectangles of this matrix.

A subrectangle is defined by two pairs of indices \((a, b)\) and \((c, d)\) such that \(1 \leq a \leq c \leq N\) and \(1 \leq b \leq d \leq M\). Its sum is computed as:

Your goal is to efficiently compute the maximum sum among all subrectangles.

inputFormat

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

The following N lines each contain M integers, separated by spaces, which represent the elements of the matrix.

outputFormat

Output a single integer, the maximum subrectangle sum, computed from the matrix.

3 3
1 2 3
4 5 6
7 8 9

45