#C2376. Largest Fertile Subrectangle

    ID: 45685 Type: Default 1000ms 256MiB

Largest Fertile Subrectangle

Largest Fertile Subrectangle

You are given a rectangular garden represented as a grid of size \(N \times M\). Each cell of the grid is either fertile (denoted by 1) or infertile (denoted by 0). Your task is to find the area of the largest contiguous subrectangle (aligned with the grid axes) that contains only fertile cells.

Input: The grid dimensions followed by the grid rows.

Output: A single integer representing the maximum area of a fertile subrectangle.

Note: The subrectangle must be contiguous and consist entirely of 1's.

For example, consider the following grid:

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

The largest fertile subrectangle has an area of 6.

inputFormat

The first line contains two space-separated integers \(N\) and \(M\), representing the number of rows and columns of the grid respectively.

The next \(N\) lines each contain \(M\) space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer which is the area of the largest contiguous subrectangle that contains only fertile cells.

## sample
4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
6