Comet OJ

C0519 [CEOI2009Day2] logs

内存限制：256 MB 时间限制：600 ms

题目描述

Given an $N \times M$ binary matrix, find the area of the biggest rectangle consisting entirely of values of $1$, knowing that you can permute the columns of the matrix.

Constraints

  • 1 ≤ N ≤ 15000
  • 1 ≤ M ≤ 1500
  • 30% of the test cases will have $N,M ≤ 1024$
  • In C/C++, it is recommended that you usefgets()to read the input.

At the end of these two pieces of code, $s$ will contain the first line of the matrix.

输入格式

The first line of the input will contain two integers separated by one space: $N$ and $M$. The following $N$ lines will contain $M$ characters of $0$ or $1$, describing the matrix.

输出

The only line of the output will contain the area of the largest rectangle.

样例

样例输入 1

10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101

样例输出 1

21

提示

Explanation

By permuting the columns such that columns 2, 4 and 5 are adjacent you have a rectangle of area 21 (rows 2-8 and columns 2, 4, 5).