题目描述

一个矩阵 $A$ 是「YF 矩阵」当且仅当满足：

• $r,s>1$
• $A_{1,1}+A_{r,s}\le A_{1,s}+A_{r,1}$

$r,s$ 分别表示矩阵 $A$ 的行数和列数。

此外，如果一个矩阵的每个大小至少为 $2\times2$ 的子矩阵都是「YF 矩阵」，我们就说这个矩阵是「Sept 矩阵」。

给定一个矩阵 $A$，你需要求出 $A$ 的含有最多元素的是「Sept 矩阵」的子矩阵所含的元素数量。

输入格式

第一行两个整数 $R,S$，分别表示 $A$ 的行数和列数。

接下来 $R$ 行每行 $S$ 个整数，描述矩阵 $A$。

输出格式

仅一行，即 $A$ 的最大的是「Sept 矩阵」的子矩阵所含的元素数量。

若这样的子矩阵不存在，输出 $0$。

3 3
1 4 10
5 2 6
11 1 3

9

3 3
1 3 1
2 1 2
1 1 1

4

5 6
1 1 4 0 3 3
4 4 9 7 11 13
-3 -1 4 2 8 11
1 5 9 5 9 10
4 8 10 5 8 8

15

提示

样例 3 说明

最大的是「Sept 矩阵」的子矩阵的左上角与右下角坐标分别为 $(3,2),(5,6)$。

数据规模与约定

• 对于 $60\%$ 的数据，有 $R,S\le 350$。
• 对于 $100\%$ 的数据，有 $2\le R,S\le 10^3$，$A_{i,j}\in[-10^6,10^6]$。

说明

按原题配置，满分 140 分。

译自 COCI 2014-2015 Contest #6 Task E NEO。