Description

You are given an $n \times m$ grid, where:

• The snake is in the bottom-left cell, denoted by Z.
• In other cells, apples are denoted by J, and empty cells are denoted by ..
• Operation A makes the snake move one step in the direction it is facing (it cannot move outside the grid).
• Operation B makes the snake move one step upward, and then its direction turns by $180\degree$.
• When the snake is on a cell with an apple, it will eat that apple.

The snake is initially facing right. Find the minimum number of operations needed for the snake to eat all apples.

Input Format

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

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

Output Format

Output one positive integer: the minimum number of operations for the snake to eat all apples.

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

7

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

15

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

5

Hint

For $100\%$ of the testdata, $2 \leq n, m \leq 1000$, and the bottom-left cell of the grid is guaranteed to be Z.

Sample 1 Explanation: Performing operations $BBAAABB$ in order can eat all apples.

Translated from COCI 2014/2015 CONTEST #5.

Translated by ChatGPT 5