Problem B. Boasting doesn't add courage ≡

Statement

Nick is a skilled swimmer. He likes to swim in the high sea with a mask. But today he faced a problem — his way was blocked by a colony of Portuguese man o' war (a species of jellyfishes).

Nick noticed that they are arranged in N rows, length of each row is M meters. There is a gleam of 1 meter between each row, in which Nick can move freely to the right or to the left. In addition, there is free cells in some rows. Nick can use them to float between rows.

Nick has an underwater camera with him. That's why he decided to float through the colony and record a video to brag to friends after that.

However, boasting doesn't add courage. Therefore Nick wants to find out the length L (in meters) of the shortest way from the 1^st to the N^th row. L contains both: movements in a row and movements between rows. Nick can start swimming in any point of the first row and finish in any point of the last row.

The distance from the current row to the next is 1 meter. Note that Nick can only swim left/right in space between rows and forward (if there is no Portuguese man o' war in front of him). For a better understanding, look at the picture that illustrates the 2_nd example. The points in the picture mark the places where Nick stops in each row between his movements (Nick can't finish his swimming in the space between the rows, so the answer is always an integer number of meters).

Input format

The first line contains two integers N and M — measurements of the jellyfish colony.

It follows by N lines, M characters each — the colony description.

By '*' marked the place with jellyfish, by '.' — free place.

It is guaranteed that each row contains no less than 1 and no more than M − 1 Portuguese man o' war.

Output format

Print integer L — the length of the Nick's shortest way through the colony.

Constraints

2 ≤ N, M ≤ 2000

Sample tests

2 2
*.
.*

2

5 7
.*****.
**.**.*
.*****.
.****.*
.**.***

8

3 5
.****
*.**.
***.*

5