345. 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 should contain two integers N and M, representing the number of rows and columns in the matrix, respectively. The next N lines should each contain M integers (either 0 or 1) to initialize 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