Maximum Rectangle Area in a Grid

In this problem, you are given a grid with N rows and M columns. Each cell in the grid is either clear (denoted by '0') or blocked by an obstacle (denoted by '1'). Your task is to compute the area of the largest rectangle that contains only clear cells.

One efficient approach is to transform each row of the grid into a histogram and then compute the largest rectangle area in that histogram. Mathematically, if we let ( h_j ) denote the height of the histogram at column ( j ), then the area of the largest rectangle in the histogram can be calculated using the formula:
[ \text{Area} = h_{\text{top}} \times \left(\text{current index} - \text{previous index in stack} - 1\right)] ]
Repeat this for each row and find the maximum area among all rows.

inputFormat

The first line contains two integers N and M representing the number of rows and columns, respectively. This is followed by N lines, each containing a string of length M consisting of the characters '0' (clear) and '1' (obstacle).

outputFormat

Output a single integer representing the area of the largest rectangle composed entirely of clear cells.## sample

4 5
00010
00110
00000
11000

6