Snake Game

Time limit1sMemory limit32 MB

Summary

Guide a snake that steps forward or climbs one row while reversing direction and eat every apple with the fewest button presses.

Level: Medium7 of 10
Topics: Dynamic programming, Shortest path, Graph
Solved: No attempts yet

Problem

Mirko is writing a clone of the computer game Snake. You move a snake on a screen of $R \times S$ pixels, and you have to eat every apple.

The rules of Mirko's version differ from the original.

The apples do not appear at random. You know the position of every apple before the game starts.
At the start the snake sits in the lower left pixel of the screen and faces right.
The game has two buttons, A and B.
Pressing A moves the snake forward by 1 pixel in the direction it currently faces. If that move would take the snake off the screen, nothing happens.
Pressing B moves the snake up by 1 pixel and turns the direction it faces by 180 degrees.
When the snake moves onto a pixel that holds an apple, it eats the apple. Unlike the original game, the snake does not grow.

Given the starting positions of the apples, find the smallest number of button presses the snake needs to eat all of them.

Input

The first line contains the height $R$ and the width $S$ of the screen ( $2 \le R, S \le 1000$ ).

Each of the next $R$ lines contains exactly $S$ characters describing the screen. A pixel with an apple is written as 'J' and an empty pixel as '.'. The first of those lines is the top row of the screen.

The lower left cell holds the character 'Z', the starting position of the snake. The screen may hold no apples at all.

Output

Print the minimum number of button presses on one line.

Hint

In the first example the shortest sequence of button presses is BBAAABB.

Examples3

Example 1
Input
```
5 5
...J.
.....
J..J.
J....
Z....
```
Expected output
```
7
```
Example 2
Input
```
5 5
.....
J...J
.J.J.
.JJJ.
Z....
```
Expected output
```
15
```
Example 3
Input
```
3 4
...J
....
Z...
```
Expected output
```
5
```