Maximum Sum Submatrix and Minimal Augmenting Submatrix

You are given a matrix of integers with n rows and m columns. Your task is to find the maximum sum of any submatrix within the given matrix. In addition, identify the smallest submatrix (by area) which, when added to the maximum sum submatrix, results in a submatrix with an even larger sum. In this problem, the augmenting submatrix is guaranteed to have an area of 1 (i.e. it is a single element with a positive value) if such an element exists.

Note: The solution always returns the area of the smallest augmenting submatrix as 1.

Detailed Explanation:

Let \(A\) be the given \(n \times m\) matrix. Define a submatrix by selecting two rows and two columns which form a contiguous block of the matrix. The sum of the submatrix is the sum of all elements inside it. The problem then requires to compute:

• \(S_{max}\): the maximum possible sum across all submatrices of \(A\).
• \(area\): the area of a smallest submatrix which, if added (as a positive integer) to the maximum sum submatrix, would result in a strictly higher sum. In our setting, this area is always 1.

You are to output \(S_{max}\) and the number 1, separated by a space.

inputFormat

The first line of the input contains two space-separated integers (n) and (m), representing the number of rows and columns respectively. Each of the following (n) lines contains (m) space-separated integers, representing the matrix elements.

outputFormat

Output a single line containing two space-separated integers: the maximum sum of any submatrix and the area of the smallest augmenting submatrix (which is 1).## sample

3 3
1 2 3
4 5 6
7 8 9

45 1