P7958 [COCI 2014/2015 #6] NEO

A matrix $A$ is a "YF matrix" if and only if it satisfies: - $r,s>1$. - $A_{1,1}+A_{r,s}\le A_{1,s}+A_{r,1}$. Here, $r$ and $s$ are the numbers of rows and columns of matrix $A$, respectively. Also, if every submatrix of a matrix with size at least $2\times2$ is a "YF matrix", then we call this matrix a "Sept matrix". Given a matrix $A$, you need to find the number of elements in the largest submatrix of $A$ that is a "Sept matrix".

The first line contains two integers $R,S$, which are the numbers of rows and columns of $A$, respectively. The next $R$ lines each contain $S$ integers, describing matrix $A$.

Output one line: the number of elements in the largest submatrix of $A$ that is a "Sept matrix". If no such submatrix exists, output $0$.

#### Explanation for Sample 3 The top-left and bottom-right coordinates of the largest submatrix that is a "Sept matrix" are $(3,2)$ and $(5,6)$, respectively. #### Constraints - For $60\%$ of the testdata, $R,S\le 350$. - For $100\%$ of the testdata, $2\le R,S\le 10^3$, and $A_{i,j}\in[-10^6,10^6]$. #### Notes According to the original problem settings, the full score is 140 points. Translated from **[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task E _**NEO**_. Translated by ChatGPT 5