Largest Zero Submatrix

Interview

Time limit2sMemory limit128 MB

Summary

Given a binary matrix, find the maximum area rectangle of consecutive rows and columns that contains only zeros.

Level: Medium6 of 10
Topics: Stack, Dynamic programming, Matrix, Array
Solved: No attempts yet

Problem

You are given an N x M matrix containing only 0 and 1. Choose a rectangular submatrix made of consecutive rows and columns whose every cell is 0. Print the largest possible area of such a submatrix.

Input

The first line contains two integers N and M. (1 <= N, M <= 333) Each of the next N lines contains a string of length M. Each character is 0 or 1 and represents one cell of the matrix without spaces.

Output

Print the maximum area of a submatrix whose cells are all 0.

Examples1

Example 1
Input
```
3 3
000
001
100
```
Expected output
```
4
```