说明

Jack 计划翻新他的房子，以使得他的房间尽可能大。然而，由于 Jack 没有太多钱，他希望以最小的努力创建一个宽敞的房间。

Jack 的房子用一个高度为 $H$、宽度为 $W$ 的网格表示。网格中的每个单元格处于以下状态之一：

• . ：地板，Jack 可以自由通过。
• # ：墙壁，Jack 无法通过。
• S ：Jack 当前所在的位置，也是一个地板单元格。

Jack 可以移动到网格中相邻（上、下、左、右）的地板单元格。他不能移动到房子的边界之外。

在这次翻新中，Jack 可以破坏至多一面墙，将其变为地板。确定在做出这一改变后，Jack 从当前位置能够到达的最大单元格数量。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} & H \ W \\ & l_{1} \\ & l_{2} \\ & \vdots \\ & l_{H} \end{aligned}$$

第一行包含两个整数 $H$ 和 $W$，分别表示网格的高度和宽度。$H$ 和 $W$ 均在 $2$ 到 $500$ 之间（含端点）。

接下来的 $H$ 行每行包含一个长度为 $W$ 的字符串，表示网格。每个字符串 $l_{i}$ 由字符 .（地板）、#（墙壁）和 S（Jack 的起始位置）组成。保证网格中恰好包含一个 S。

输出格式

输出一个整数，表示 Jack 在可选地破坏一面墙后，从起始位置能够到达的最大单元格数量。

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

6

3 7
.......
...S...
.......

21

提示

翻译由 DeepSeek V3.2 完成