Uolevi is playing a video game. He has already defeated all the enemies of a level, and now he wants to collect all coins of the level to get the high score.

The level is a two-dimensional grid consisting of n rows and m columns. In one step Uolevi can move down or right. If Uolevi is located in a same cell with a coin, Uolevi collects it. Uolevi can use teleport at the cell in lower right corner to teleport to upper left corner. At the beginning Uolevi is located at upper left corner and after collecting the coins he has to move to lower right corner. What is the lowest number of steps required to collect all coins?

Input

The first line contains two integers: n and m, denoting the number of rows and the number of columns in the level.

Each of the next n rows contains a string of length m representing a row of the level, where each character represents the content of a single cell:

• '.' An empty cell
• 'C' A cell initially containing a coin

Output

Output a single integer, the lowest number of steps required to collect all coins.

Constraints

• 2 \le n,m \le 2000
• There is at least 1 and no more than 2000 coins

Examples

Input:

4 5
..C..
...C.
.C.C.
C....

Output:

21

Input:

3 3
C..
.C.
..C

Output:

4