Problem Description

Mirko is playing a modified version of the Snake game.

Problem Description

You are given a matrix of size $n \times m$, where:

• The snake is located at the bottom-left corner, represented by Z;
• Other cells contain apples represented by J and empty spaces represented by .;
• Operation A moves the snake one step in the direction it is facing (it cannot move out of the matrix);
• Operation B moves the snake one step upwards and rotates its direction by $180$ degrees;
• When the snake is on a cell with an apple, it eats the apple.

The snake starts facing right. Determine the minimum number of operations required for the snake to eat all the apples.

Input Format

The first line contains two positive integers $n$ and $m$.

The next $n$ lines each contain a string of length $m$, consisting only of characters ., J, and Z, representing the matrix.

Output Format

A single positive integer representing the minimum number of operations required for the snake to eat all the apples.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

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

Sample Output #2

15

Sample Input #3

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

Sample Output #3

5

Notes

For $100\%$ of the data, $2 \leq n, m \leq 1000$, and the bottom-left corner of the matrix is always Z.

Sample 1 Explanation: Executing operations $BBAAABB$ in sequence will eat all the apples.

Translated from COCI 2014/2015 CONTEST #5.

见题面 Input 部分

见题面 Output 部分