9013 - 找天坑

人类世界经历了旷日已久的干旱,雨师玄冥决定下一场雨来缓解人间的干旱。由于各种条件的限制,你只能用一种正方体砖在地平面上垒一个盛水的容器,等待雨师下雨时,用于积水。因为看起来像天坑,所以我们称为“找天坑”。

实际的情况更为糟糕,你能用的砖块已经被一个熊孩子以搭积木的形式搭在一个mn列的矩形范围内。你现在需要做的是,在这mn列的范围内,找到一个天坑,使得所盛的雨水体积最大。

砖头之间是无缝连接的.即只需要4块砖便可以垒出一个能盛放1体积雨水的天坑,如图所示。

15672599411024.png

 

输入

第一行包含两个整数mn,分别表示矩形区域砖块的行数和列数。

后面包括m行数据,每一行有n个非负整数,数字之间以空格相隔。每个数字表示该位置所放置的砖块高度(即堆放正方体砖块的数量)。

输出

找出最大的那个天坑所能盛放雨水的体积。

样例

输入

3 3
0 1 0
1 0 1
0 1 0

输出

1

输入

3 3
1 1 1
1 0 1
1 1 0

输出

1

输入

3 6
1 6 1 0 1 1
1 0 0 1 0 0
1 5 0 4 1 1

输出

0

提示

对于100%的数据:n,m\leq 10^3

来源

本站月赛

时间限制 2 秒
内存限制 128 MB
讨论 统计
上一题 下一题