Maximal Rectangle in a Binary Matrix

Given a binary matrix (composed of 0's and 1's), your task is to compute the area of the largest rectangle that contains only 1's. The rectangle must be formed by adjacent cells in the matrix. To solve this problem efficiently, consider using a histogram based approach with a stack to compute the maximal rectangle area for each row.

You are expected to implement a solution that reads input from standard input, processes the matrix, and outputs the area of the largest rectangle to standard output.

inputFormat

The first line of input contains two integers, m and n, which represent the number of rows and columns of the matrix respectively.

This is followed by m lines, each containing n space-separated integers (0 or 1) representing the binary matrix.

outputFormat

Output a single integer representing the area of the largest rectangle that contains only 1's.

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

6