Snake Apple Collection

You are given an \(n\times m\) grid. In the grid, the snake is initially located in the bottom‐left cell and is denoted by Z. Other cells may either contain an apple, denoted by J, or be empty (denoted by .).

The snake has a facing direction. Initially the snake faces to the right. There are two types of operations you can perform:

• Operation A: The snake moves one cell in the direction it is currently facing. (The snake cannot move outside the grid.)
• Operation B: The snake moves one cell upward and then its facing direction is reversed (rotated by \(180^\circ\)).

Whenever the snake moves into a cell containing an apple, it eats the apple (the cell thereafter is considered empty).

Your task is to compute the minimum number of operations (each operation counts as one move) needed for the snake to eat all the apples in the grid.

Important note about movement: The snake does not have full control of its turning. It can only change its horizontal direction when performing an Operation B; note that Operation B always moves the snake upward by exactly one cell. This implies that while moving horizontally in any given row, the snake cannot reverse its horizontal direction. As a consequence, in any row that the snake visits, the apples (if any) are reachable only if they lie in the direction in which the snake is moving. For example, since the snake starts in the bottom row facing right, any apple in that row must lie to the right of the starting position. Similarly, when the snake ascends one row by Operation B, its direction flips, so in the next row it can only move in the opposite direction.

The coordinate system is defined so that the bottom row is row \(0\) and the top row is row \(n-1\); columns are numbered from \(0\) (left) to \(m-1\) (right). The grid is given in standard input with the first line corresponding to the top row and the last line corresponding to the bottom row. It is guaranteed that the input is such that all apples can be collected.

Input is read from standard input and output is written to standard output.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns).

The following \(n\) lines each contain a string of length \(m\) consisting of the characters Z, J, and ..

Note that in the input the top row is given first and the bottom row is given last. The snake (marked by Z) always appears in the bottom‐left cell (i.e. in the last line, first character).

outputFormat

Output a single integer, which is the minimum number of operations required for the snake to eat all the apples.

sample

1 5
ZJJJ.

3