Mirko 正在制作一款流行电脑游戏“贪吃蛇”的克隆版本。在游戏中，你控制一条蛇在尺寸为 $R \times S$ 像素的屏幕上移动。游戏的目标是收集所有的苹果。

不幸的是，Mirko 的实现并不是很好，游戏玩法与原版不同。以下是 Mirko 游戏的描述：

• 与原版不同，苹果不会随机出现在屏幕上，而是在游戏开始时你就知道所有苹果的位置。
• 在游戏开始时，蛇位于屏幕的左下角像素，并且朝向右侧。
• 游戏中有两个按钮，分别记为 A 和 B。
• 当你按下按钮 A 时，蛇会向其当前面对的方向前进 1 个像素。如果该移动会导致蛇移出屏幕，则什么也不会发生。
• 当你按下按钮 B 时，蛇会向上移动 1 个像素，并将其面对的方向旋转 180°。
• 当蛇移动到含有苹果的像素时，它会吃掉苹果，但不会像原版游戏那样长大。

你的任务是：给定游戏开始时苹果的位置，确定蛇收集所有苹果所需的最少按键次数。

输入格式

输入的第一行包含整数 $R$ 和 $S$（$2 \le R, S \le 1000$），表示屏幕的高度和宽度。

接下来的 $R$ 行，每行包含恰好 $S$ 个字符。这些字符表示屏幕的内容。有苹果的像素用字符 'J' 表示，空像素用字符 '.' 表示。

左下角包含字符 'Z'，表示蛇的初始位置。

输出格式

输出的第一行也是唯一的一行，必须包含所需的最少按键次数。

样例

输入样例 1

5 5
...J.
.....
J..J.
J....
Z....

输出样例 1

7

输入样例 2

5 5
.....
J...J
.J.J.
.JJJ.
Z....

输出样例 2

15

输入样例 3

3 4
...J
....
Z...

输出样例 3

5

说明

第一个样例的解释：蛇收集所有苹果所需的最短按键序列为 BBAAABB。