Maximal Rectangle

You are given a 2D grid (matrix) of integers that contains only 0s and 1s. Your task is to find the area of the largest rectangular submatrix that consists entirely of 1s.

Let the matrix be represented as \(A\) with \(r\) rows and \(c\) columns. The solution involves computing, for each row, an auxiliary histogram that represents the number of consecutive 1s in the column up to that row. Then, by applying the well-known largest rectangle in histogram algorithm, you can determine the maximal area rectangle for that row. The final answer is the maximum area found over all rows.

Formally, for a given matrix \(A\), you should compute:

\[ \text{maxArea} = \max_{0 \leq i < r} \{ \text{largestRectangleArea}(H_i) \} \]

where \(H_i\) is the histogram array at row \(i\), and the function largestRectangleArea computes the largest rectangle area in a histogram.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers \(r\) and \(c\) separated by a space, where \(r\) is the number of rows and \(c\) is the number of columns in the matrix.
• Each of the next \(r\) lines contains \(c\) space-separated integers (each being either 0 or 1) representing a row of the matrix.

outputFormat

Output a single integer to stdout: the area of the largest rectangular submatrix that contains only 1s.

## sample

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

6