QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

#6584. The Carpet

Statistics

Byteasar is visiting a carpet store looking at a certain carpet. Unfortunately, some fragments of the carpet are looking unsightly, due to factory defects. Because Byteasar would like to buy a substantial amount of the floor covering, he decided to allow himself to buy carpet with no more than one faulty spot. He will cover such a defect with a large flower-pot and the problem would be gone.

For simplicity, the carpet available in the store is represented as a rectangle with a height of $h$ and width $w$, divided into $h \times w$ squares of size $1 \times 1$. We know whether each carpet square has a defect, or not. Byteasar would like to buy a rectangular carpet piece which is as large as possible, consisting of square units, wherein at most one square is faulty. What is the area of such a piece?

Input

The first line of input contains two integers $h$ and $w$ ($1\leq h, w \leq 2000$), denoting respectively the height and width of the carpet available in the store.

Subsequent $h$ rows describe the carpet.

Each of these lines contains a string of $w$ characters . (square without faults), and # (faulty square), describing the individual carpet squares.

Output

Output the maximum area of a rectangular piece of the carpet, which consists of unit squares and has one defective square at most.

Examples

Input

4 5
#.#..
....#
..#..
....#

Output

12

Discussions

About Discussions

The discussion section is only for posting: Editorials, 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. Submitting multiple issues may cause your account to be banned.
  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.