Description

YONG-IN Hall is a rectangular grid area. Each sponsor's exhibition booth occupies several unit cells. The $\text{I}$-shaped awards podium will be built upright, and its sides are parallel to the edges of YONG-IN Hall. An $\text{I}$-shaped podium is formed by connecting three rectangles, where the rectangles at the top and bottom must extend beyond the middle rectangle on both left and right sides; otherwise, it will be mistaken for letters such as $\text{T, L, J}$. For example:

These are two valid $\text{I}$-shaped podiums, while the following three cases are all invalid:

You are asked to write a program to find the $\text{I}$-shaped podium with the maximum area such that it does not cover any exhibition booth.

Input Format

The first line contains two positive integers $n,\,m$, representing the number of rows and columns of the rectangular grid area of YONG-IN Hall.

In the next $n$ lines, each line contains $m$ digits $p_{i,\,j}$. Each digit describes a unit cell: $1$ means there is an exhibition booth in this cell, and $0$ means there is no exhibition booth in this cell.

Output Format

Output only one positive integer, the area of the largest $\text{I}$-shaped podium. If there is no valid $\text{I}$-shaped podium, output $0$.

6 8
1 1 1 1 1 0 0 1
1 0 0 0 0 1 1 1
1 0 0 0 0 0 1 1
1 0 1 0 1 0 1 0
1 0 0 0 0 0 0 1
1 1 0 0 0 1 0 1

15

Hint

For $100\%$ of the data, $1 \leq n,\,m \leq 200$, $p_{i,\,j} \in \{0,\,1\}$.

Sample explanation:

The maximum selectable $\text{I}$-shaped podium area is $15$.

Translated by ChatGPT 5