QOJ.ac

QOJ

Límite de tiempo: 2 s Límite de memoria: 128 MB Puntuación total: 100

#15860. Award Ceremony

Estadísticas

The IOI 2002 awards ceremony will be held in the YONG-IN Hall. After the excitement of the World Cup, people are in high spirits. To make the ceremony more attractive, it has been suggested to build an I-shaped podium in the YONG-IN Hall to represent Informatics. Considering that the competition sponsors may have placed many display stands in the YONG-IN Hall, they may be unwilling to move them. As the gold medalist of IOI 2002, you have naturally become the person they turn to for help.

The YONG-IN Hall is a rectangular grid area. Each sponsor's display stand occupies a certain number of unit cells. The I-shaped podium will be built upright and parallel to the edges of the YONG-IN Hall. An I-shaped podium is formed by three rectangles connected together, where both sides of the top and bottom rectangles must extend beyond the middle rectangle; otherwise, it would be misinterpreted as letters such as T, L, or J. For example:

These are two valid I-shaped podiums, while the following three cases are invalid:

The right side of the bottom rectangle does not extend beyond the middle rectangle, which would be misinterpreted as J

Rectangles are not connected, invalid

A 90-degree rotated podium is invalid, which would be misinterpreted as H

You are expected to write a program to find the I-shaped podium with the largest area that does not cover any display stands.

Input

The first line of the input contains two positive integers $n$ and $m$ ($1 \le n, m \le 200$), representing the number of rows and columns of the rectangular grid area of the YONG-IN Hall, respectively. The following $n$ lines each contain $m$ numbers, either $0$ or $1$. Each number describes a unit cell, where $1$ indicates that the unit cell contains a display stand, and $0$ indicates that the unit cell does not contain a display stand.

Output

The output contains only one integer, representing the area of the largest I-shaped podium. If no valid I-shaped podium exists, output $0$.

Examples

Input 1

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

Output 1

15

Note

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.