738. Largest Rectangular Island

0

Hard

Given a matrix representing a sea, where each block contains either 0 (representing water) or 1 (representing an island), we need to find the largest rectangular block (island) in the sea. The goal is to determine the area of the largest rectangle that contains only 1's. Each block in the matrix has an area of 1x1.

Input Format

The first line of input contains two integers, N (the number of rows) and M (the number of columns) of the matrix. The next N lines contain M integers each, either 0 or 1, representing the matrix.

Output Format

Print the area of the largest rectangular island in the sea.

Example

Input

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

Output

6

Constraints

1 <= row, cols <= 200

matrix[i][j] is '0' or '1'.

matrix[i][j] is '0' or '1'.

Loading...

View Submissions

Console