최대 직사각형

0 0이 나올 때까지 각 이진 행렬에서 1로만 이루어진 가장 큰 직사각형 넓이를 구합니다.

보통6스택행렬동적 계획법아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제

0과 1로 이루어진 N×MN \times M 크기의 행렬이 주어진다. 원소가 모두 1인 부분 직사각형 가운데 넓이가 가장 큰 것의 넓이를 구하라.

부분 직사각형은 연속한 행 구간과 연속한 열 구간이 만나는 영역이고, 넓이는 그 안에 들어 있는 칸의 개수다.

입력

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 NNMM이 주어진다 (1N,M10001 \le N, M \le 1000). 이어지는 NN개 줄에는 각 행의 원소 MM개가 공백으로 구분되어 주어지며, 각 원소는 0 또는 1이다.

마지막 줄에는 0이 두 개 주어진다. 이 줄은 테스트 케이스가 아니다.

출력

각 테스트 케이스마다 원소가 모두 1인 가장 큰 직사각형의 넓이를 한 줄에 하나씩 출력한다. 그런 직사각형이 없으면 0을 출력한다.