Code Submission Evaluation System Login

CSES - HIIT Open 2016 Practice

HIIT Open 2016 Practice

Contest start:2016-05-19 17:00:00
Contest end:2016-05-28 9:00:00

Task list | Submit code | Submissions | Scoreboard | Statistics


High score

Time limit:1.00 s
Memory limit:128 MB

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: Output

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

Constraints
Examples

Input:
4 5
..C..
...C.
.C.C.
C....


Output:
21

Input:
3 3
C..
.C.
..C


Output:
4