Gennadiy 在他最喜欢的游戏中想出了一个新的挑战：在不触碰地面的情况下通关。

在游戏中，关卡是一个由网格组成的地图。每个格子要么是空的，要么填满了地面。在空格子中，可能会有怪物、关卡入口或关卡出口。游戏地图之外的所有区域都填满了地面。怪物无法移动。

尽管关卡是以网格形式呈现的，但游戏时间是连续流逝的，玩家在地图上的移动也是连续的。假设玩家是一个点。由于披风的存在，玩家总是以极慢的恒定速度向下移动。披风允许玩家滑翔：除了无法改变的垂直分速度外，玩家可以在任何时刻任意选择水平分速度。玩家不能穿过地面格子，并且在挑战中，玩家甚至不能触碰地面。

枪只能用来向左或向右射击。子弹从枪中射出，并在指定的方向上水平飞行，直到首次接触到地面。子弹路径上所有格子中的怪物都会被消灭。

要通过关卡，玩家必须从关卡入口所在的格子飞到出口所在的格子。允许从入口格子内的任意点开始，并在出口格子内的任意点结束。Gennadiy 需要知道他是否能做到这一点，如果能，他在这个过程中最多可以消灭多少只怪物。

玩家可以拥有任意高的水平速度。枪拥有无限子弹，并且可以根据需要以任意快的速度射击。玩家可以飞过含有怪物的格子，这也会消灭该怪物。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ —— 分别表示地图的垂直和水平大小（$1 \le N, M \le 2\,000$）。

接下来的 $N$ 行，每行包含 $M$ 个字符，描述游戏地图。每个字符描述对应格子的内容：

• @ — 地面格子。
• . — 空格子。
• m — 有怪物的空格子。
• S — 有关卡入口的空格子。
• E — 有关卡出口的空格子。

保证关卡中只有一个入口格子和一个出口格子。

输出格式

如果无法飞越关卡，输出 -1；否则输出在此过程中最多可以消灭的怪物数量。

样例

输入样例 1

9 11
..m...S....
..@.@...@@.
..@m@@...@.
..@@...@...
[email protected]@.m.
.@@[email protected]@.
..@@m@@.@..
...m.m....E
...@.@@.m..

输出样例 1

7

输入样例 2

3 1
S
@
E

输出样例 2

-1

说明

第一个样例中通关的最优方案如下图所示。请注意，禁止在两个地面格子之间沿对角线飞过。

在第二个样例中，入口和出口之间的路径被阻挡，因此无法飞越关卡。

第一个样例的最优通关方案