给定一个由数字 0 和 1 组成的矩阵,其大小为 n × m。您可以重新排列其行。在给定问题中通过所描述的操作可以获得仅由 1 组成的子矩阵的最大面积是多少?
假设矩阵 a 的行从上到下编号为 1 到 n,列从左到右编号为 1 到 m。第i行和第j列相交处的矩阵单元可以表示为(i,j)。形式上,矩阵 a 的子矩阵是一组四个整数 d、u、l、r (1 ≤ d ≤ u ≤ n;1 ≤ l ≤ r ≤ m)。我们假设子矩阵包含单元 (i, j) (d ≤ i ≤ u; l ≤ j ≤ r)。子矩阵的面积是它包含的单元数。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 5000)。接下来的 n 行每行包含 m 个字符 - 矩阵 a。矩阵a仅包含字符:“0”和“1”。请注意,矩阵的元素后面的行中没有任何空格。
输出
打印单个整数——获得的最大子矩阵的面积。如果我们无法获得数字为 1 的矩阵,则打印 0。
示例
输入 #1
1 1 1
输出 #1
1
输入 #2
2 2 10 11
输出 #2
2
输入 #3
4 3 100 011 000 101
输出 #3
2