题目描述

《地城探宝: 纸汤》（neta《地城探宝: 石头汤》）已经成为了最流行的游戏，并且你要试玩一下。这个游戏在一个 $N$ 行 $M$ 列的矩形场地上进行，每个单元格可能是如下类型之一：

• 空单元格 .
• 墙壁 #
• 金币 o
• 可爆炸的地雷 X
• 起点 S

保证第一行，第一列，最后一行和最后一列只包含墙壁（注意，玩家不能穿墙移动）。场地中可能有一个或更多起点。当游戏开始时，玩家会处于某一个标记为 S 的起点。因为游戏是在地下城中进行，可见度是有限的，因此玩家看不见整个地图，只能看见以他为中心的 $3\times 3$ 方形区域。同时，对于玩家来说地雷和起点看上去和空单元格一样（它们都是不可见的）。

每次移动，玩家只能移动到东西南北四个方向的相邻格子中。如果玩家进入了一个有金币的格子，那么金币会被收集，之后就会从格子中消失。如果玩家进入了有地雷的格子，那么地下城就会崩塌，玩家会失去所有获得的金币，游戏就结束了。

好消息是经过查网上攻略，你获得了地下城的地图。然而你不知道你的起点会是哪儿——但是保证你会从某个起点出发。如果你以最优策略进行游戏，你可以保证最多会获得多少金币（再次，你不知道你的起点是哪个）？

---

输入格式

第一行两个正整数 $N$ 和 $M$。

接下来 $N$ 行，每行 $M$ 个字符，表示地下城的地图。

---

输出格式

输出一个整数，表示在不知道起点位置的情况下，最多可以获得的金币个数。

---

样例 1

输入

3 7
#######
#Soooo#
#######

输出

4

地图上只有一个起点，因此我们知道玩家会从哪里开始。这种情况下玩家可以收集所有金币。

---

样例 2

输入

3 8
########
#SoXooS#
########

输出

1

地图上有两个起点，玩家可以通过在起点所看到的来推断是从哪个起点出发的（@ 是玩家所处的位置）：

###     ###
#@o     o@#
###     ###

如果从左侧位置出发，最多能收集 $1$ 个金币，如果从右侧位置出发，最多能收集 $2$ 个金币。因此最坏情况下我们能收集 $1$ 个金币。

---

样例 3

输入

7 18
##################
#................#
#.o...SX.......o.#
#.o...X..X.....o.#
#.o.....XS.....o.#
#................#
##################

输出

0

不管出发位置，在最坏情况下，玩家会踩到地雷后输掉游戏。玩家初始看到的区域是：

...
.@.
...

---

样例 4

输入

7 18
##################
#....#...........#
#.o...SX.......o.#
#.o...X..X.....o.#
#.o.....XS.....o.#
#.........#......#
##################

输出

6

根据墙壁的位置（左上或右下），玩家可以判断出自己的起点位置并安全地获得所有 $6$ 枚金币。玩家初始看到的区域将会是下面两个中的一个：

#..     ...
.@.     .@.
...     ..#

---

样例 5

输入

7 18
##################
#......X..S....oo#
##################
#..o..S.X......o.#
##########X#######
#o.....S...X.....#
##################

输出

1

玩家向左移动两个格子，如果玩家看到了金币，那么他在第四行，所以玩家会获得这个金币。

否则，玩家仍然不知道自己是在第二行还是第六行，所以玩家向右移动四格，如果玩家看见右上角的格子是空的（地雷格显示为空格），那么他就在第六行，所以他会向左移动获得金币。

如果玩家没有在右上角看到一个空格子，那么玩家会向右移动获得两个金币，因为此时玩家在第二行。因此，收集到的最少金币数为 $1$。

我们可以观察到第一步向右走是危险的，因为玩家可能会在从相邻格子获得信息之前进入中间一行的地雷格。

---

数据范围与提示

令 $S$ 为地图上可能的起点数量

• $N \le 400, M \le 400, S \le 60$

#	分值	限制
1	3	$S=1$。没有地雷。除了第一行，第一列，最后一行和最后一列外没有墙壁
2	7	$N=3$
3	12	$S=1$
4	23	$S=2$
5	41	$1 \le N,M \le 250, 1 \le S \le 12$
6	14	无附加限制

---