Maximal Rectangle of 1s in a Binary Matrix

You are given a binary matrix of size \(N \times M\) where each element is either 0 or 1. Your task is to compute the area of the largest rectangle (sub-matrix) that contains only \(1\)s.

The rectangle must be formed by contiguous cells in the matrix. For example, consider the matrix below:

1 0 1 1
1 0 1 1
1 1 1 1
1 0 0 1

The maximum rectangle of all 1s has an area of 6.

If the matrix is empty or there is no rectangle made entirely of 1s, output 0.

Input/Output Format: Solve the problem by reading the input from stdin and writing the answer to stdout.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of rows and columns of the matrix respectively. \(N\) can be 0, in which case the matrix is empty. The following \(N\) lines each contain \(M\) integers separated by spaces representing the matrix rows. Each integer is either 0 or 1.

Example:

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

outputFormat

Output a single integer denoting the area of the largest rectangle containing only 1s.

## sample

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

6