No submission language available for this problem.

Background

Special for beginners, ^_^

Description

有一个行数为 $H$ 列数为 $W$ 的网格。有些单元格（可能为零）包含磁铁。

网格的状态由长度为 $W$ 的 $H$ 个字符串 $S_1, S_2, \ldots, S_H$ 表示。

如果 $S_i$ 的第 $j$ 个字符是 "#"，则表示在从上往下的第 $i$ 行和从左往右的第 $j$ 列的单元格中有磁铁；

如果是 "."，则表示单元格是空的。

身穿铁甲的关小山可以在网格中做如下移动：

• 如果与当前单元格垂直或水平相邻的任何一个单元格中含有磁铁，他就不能移动。
• 否则，他可以移动到任何一个垂直或水平相邻的单元格。
  但是，他不能离开网格。

对于每个没有磁铁的单元格，将其自由度定义为他从该单元格重复移动所能到达的单元格数。求网格中所有没有磁铁的单元格的最大自由度。

这里，在自由度的定义中，"他可以通过重复移动到达的单元格 "指的是从初始单元格通过一定的移动序列（可能是零移动）可以到达的单元格。不一定要有一个移动序列能从初始单元格开始访问所有这些可到达的单元格。具体来说，每个单元格本身（没有磁铁）总是包含在从该单元格可到达的单元格中。

Format

Input

输入

$H$ $W$

$S_1$

$S_2$

$\vdots$

$S_H$

Output

打印关小山可以移动的最大自由度。

Samples

3 5
.#...
.....
.#..#

9

3 3
..#
#..
..#

1

Limitation

• $1 \leq H, W \leq 1000$
• $H$ 和 $W$ 是整数。
• $S_i$ 是长度为 $W$ 的字符串，由 . 和 # 组成。
• 至少有一个单元格没有磁铁。

1s, 1024KiB for each test case.