Largest Rectangle Area in a Binary Matrix

You are given a binary matrix (a matrix that only contains 0's and 1's) with N rows and M columns. Your task is to compute the area of the largest rectangle containing only 1's.

The first line of the input contains two space-separated integers, N and M, representing the number of rows and columns respectively. Each of the following N lines contains M integers (either 0 or 1) separated by spaces.

If we denote the height of a column in the rectangle by h and the width by w, then the area of that rectangle is given by the formula: $$area = h \times w$$.

Your program should output a single integer which is the maximum area of a rectangle containing only 1's in the matrix. If there is no such rectangle, output 0.

inputFormat

The input is read from standard input (stdin). The first line contains two integers N and M (separated by a space) - the number of rows and columns of the matrix. Each of the next N lines contains M integers (either 0 or 1) separated by spaces.

outputFormat

Output a single integer to standard output (stdout) representing the area of the largest rectangle that contains only 1's.

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

4