题目描述

我们有一个 $H$ 行 $W$ 列的网格。第 $i$ 行（$1≤i≤H$）第 $j$ 列（$1≤j≤W$）的状态用字母 $a_{ij}$ 表示，状态如下：

• .：该单元格为空。
• o：该单元格包含机器人。
• E：该单元格包含出口。整个网格中只出现一次 E。

Snuke试图尽可能多地拯救机器人，通过执行以下操作几次：

• 选择以下方向之一：上、下、左、右。所有剩余的机器人都将沿着选定的方向移动一个单元格，除非机器人将走出网格，否则机器人将爆炸并立即从网格中消失。如果机器人移动到包含出口的单元格，则机器人将被拯救并立即从网格中移除。

找出可以拯救的最大机器人数量。

约束条件

• $2≤H,W≤100$
• $a_{ij}$ 为 ., o 或 E。
• 整个网格中只出现一次 E。

输入

输入的格式如下，从标准输入给出：

$H$ $W$ $a_{11}$$...$$a_{1W}$ $:$ $a_{H1}$$...$$a_{HW}$

输出

打印可以拯救的最大机器人数量。

示例输入1

3 3
o.o
.Eo
ooo

示例输出1

3

例如，选择左、上、右。

示例输入2

2 2
E.
..

示例输出2

0

示例输入3

3 4
o...
o...
oooE

示例输出3

5

选择右、右、右、下、下。

示例输入4

5 11
ooo.ooo.ooo
o.o.o...o..
ooo.oE..o..
o.o.o.o.o..
o.o.ooo.ooo

示例输出4

12