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

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.