#1540. 最大空白区

最大空白区

问题描述

小明有一张 N*M 的方格纸,且部分小方格中涂了颜色,部分小方格还是空白。

给出 N(2≤N≤30)和 M(2≤M≤30)的值,及每个小方格的状态(被涂了颜色小方格用数字 1 表示,空白小方格用数字 0 表示),请帮助小明找出最大的矩形空白区域,并输出矩形空白区域由多少个小方格组成。

例如:N=4,M=5,4*5 的方格纸中每个小方格的状态如下图: image

最大的空白区域由 6 个小方格组成(红色框区域)。

格式

输入

第一行输入两个正整数 N 和 M(2≤N≤30,2≤M≤30),分别表示方格纸的行数和列数,两个正整数之间以一个空格隔开

第二行开始输入 N 行,每行 M 个整数(整数为 1 或者 0),1 表示涂色方格,0 表示空白方格,整数之间以一个空格隔开

输出

输出一个整数,表示最大矩形由多少个小方格组成(如果没有空白小方格,输出 0)

样例

4 5 

1 1 0 0 0 

1 0 1 0 0 

0 0 0 1 1 

0 0 0 1 0
6

提示

数据范围、额外说明、样例说明等等