QOJ.ac

QOJ

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

#6584. Wykładzina

統計

Bajtazar ogląda właśnie w sklepie wykładzinę. Niestety na niektórych fragmentach wykładziny są brzydko wyglądające wady fabryczne. Ponieważ Bajtazar chciałby zakupić jak najwięcej wykładziny, postanowił, że dopuszcza kupienie wykładziny z jedną wadą. Postawi w tym miejscu dużą donicę z kwiatami i nie będzie problemu.

Dla uproszczenia wykładzinę dostępną w sklepie reprezentujemy jako prostokąt o wysokości $w$ i szerokości $s$ podzielony na $w \times s$ kwadracików o rozmiarach $1 \times 1$. Dla każdego kwadracika wiemy, czy zawiera on wadliwy fragment wykładziny. Bajtazar chciałby kupić jak największy prostokątny kawałek wykładziny składający się z kwadracików jednostkowych, w którym co najwyżej jeden kwadracik jest wadliwy. Ile wynosi pole powierzchni takiego kawałka?

Input Format

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $w$ i $s$ ($1 \le w, s \le 2\,000$), oznaczające odpowiednio wysokość i szerokość wykładziny dostępnej w sklepie. Kolejne $w$ wierszy opisuje wykładzinę. Każdy z tych wierszy zawiera napis składający się z $s$ znaków . (kwadracik bez wad) i # (kwadracik wadliwy), który opisuje poszczególne kwadraciki jednostkowe wykładziny.

Output Format

Wypisz maksymalne pole powierzchni prostokątnego kawałka wykładziny, który składa się z kwadracików jednostkowych i zawiera co najwyżej jeden wadliwy kwadracik.

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.