题目背景

Mirko 在玩魔改的贪吃蛇。

题目描述

给你一个 $n\times m$ 的矩阵，其中：

• 蛇在左下角，用 Z 表示；
• 其他格子苹果用 J 表示，空白用 . 表示；
• 操作 A 让蛇向它面对的方向走一步（不能走出矩阵）；
• 操作 B 让蛇向上走一步，并且方向转 $180\degree$；
• 当蛇所在格子有苹果时，蛇会把这个苹果吃掉。

现在蛇面向右，求最少操作数使蛇吃掉所有苹果。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，只含 ., J, Z ，表示该矩阵。

输出格式

一个正整数，表示蛇吃掉所有苹果的最少操作数。

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

7

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

15

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

5

提示

对于 $100\%$ 的数据，$2 \leq n,m \leq 1000$，矩阵的左下角一定是 Z。

样例 1 解释： 依次执行操作 $BBAAABB$ 可吃掉所有苹果。

译自 COCI 2014/2015 CONTEST #5。