Rectangular Dry Land

Interview

Time limit7sMemory limit1024 MB

Summary

Given a binary grid of wet and dry cells, find the area of the largest rectangle made only of dry cells.

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

Problem

Florida has many wetlands, so finding space to build houses is difficult. The problem is worse when people insist that their houses be rectangular.

The land is a two-dimensional rectangular grid, and each cell is either wet or dry. Find the largest rectangular dry area, that is, the largest house you can build by area. The house must be rectangular, so the dry cells you use must form a rectangle, and that rectangle cannot contain any wet cells.

Input

The first line contains two integers $r$ ( $1 \le r \le 200$ ) and $c$ ( $1 \le c \le 200$ ), the number of rows and columns of the land.

Each of the next $r$ lines describes one row. Each line has $c$ characters, starting from column 1. Each character is either 1 (wetland) or 0 (dryland).

Output

Print the area of the largest rectangular dryland.

Examples3

Example 1
Input
```
4 5
10010
01111
11110
00001
```
Expected output
```
6
```
Example 2
Input
```
3 2
10
11
11
```
Expected output
```
4
```
Example 3
Input
```
2 2
10
01
```
Expected output
```
1
```