#K82142. Largest Rectangle in a Grid

    ID: 35910 Type: Default 1000ms 256MiB

Largest Rectangle in a Grid

Largest Rectangle in a Grid

You are given a grid with (n) rows and (m) columns. Each cell in the grid is either '1' representing fertile land or '0' representing barren land. Your task is to determine the area of the largest rectangular region composed entirely of fertile cells.

The area of a rectangle is given by (A = l \times w), where (l) is the rectangle's length and (w) its width. The rectangle must be formed by contiguous cells in the grid.

For example, a grid with 3 rows and 4 columns may be provided as follows:

1011
1101
1110

In this grid, the largest rectangle of fertile land has an area of 4.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (m) representing the number of rows and columns of the grid respectively. The following (n) lines each contain a string of length (m) consisting of characters '0' and '1', where '1' indicates fertile land and '0' indicates barren land.

outputFormat

Output a single integer to standard output (stdout) indicating the area of the largest rectangular region consisting solely of '1's.## sample

3 4
1011
1101
1110
4