Maximal Rectangle

Given a binary matrix consisting of 0s and 1s, your task is to find the area of the largest rectangle containing only 1s and return its area.

You are given an integer m and n representing the number of rows and columns respectively, followed by m lines each containing n integers (either 0 or 1). You need to compute the maximum area of a contiguous subrectangle that comprises only the number 1.

The area of a rectangle is defined by its height multiplied by its width. If the matrix is empty, the answer is 0.

The optimal solution uses a histogram technique with stack processing to compute the largest rectangle in each row.

Formally, if you denote heights[i] as the number of consecutive ones ending in row i for each column, then the area can be calculated using the algorithm for largest rectangle in histogram. In LaTeX, if we define the area by A = h \times w, then our goal is to maximize A over all valid rectangles.

Input constraints: 0 ≤ m, n ≤ 10³.

inputFormat

The first line of input contains two integers m and n separated by a space — the number of rows and columns respectively.

If m is non-zero, then the next m lines each contain n integers (each being either 0 or 1) separated by spaces.

If m is 0, the matrix is empty and you should output 0.

outputFormat

Output a single integer — the area of the largest rectangle consisting only of 1s.

## sample

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

6