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
About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.