Maximum Rectangle in a Binary Grid

Given an (N \times M) grid filled with 0's and 1's, your task is to find the area of the largest rectangle that contains only 1's. The rectangle must be formed by contiguous cells and its sides should be parallel to the grid axes.

For example, consider the grid below:

(\begin{matrix}1 & 1 & 0 & 1\ 1 & 1 & 1 & 1\ 1 & 1 & 1 & 0\ 0 & 1 & 0 & 0\end{matrix})

The largest rectangle formed by 1's has an area of 6.

Input: The first line contains two integers (N) and (M). Each of the following (N) lines contains (M) integers (either 0 or 1) separated by spaces.

Output: Output a single integer representing the area of the largest rectangle consisting entirely of 1's.

inputFormat

The input is read from standard input (stdin) and consists of multiple lines. The first line contains two space-separated integers (N) and (M), denoting 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

The output should be a single integer printed to standard output (stdout) representing the area of the largest rectangle that contains only 1's.## sample

4 4
1 1 0 1
1 1 1 1
1 1 1 0
0 1 0 0

6