You are currently in your hotel at the north-west corner of Delft, and want to go to the contest site at the university in the south-east corner of Delft. To get there, you have to go right through the historical centre of the city.
Like Manhattan, the city consists of a grid of buildings. But unlike Manhattan, the city does not only contain square residential buildings but also some round medieval towers. All the square buildings are axis aligned with a side length of and all round towers have a diameter of . There is just enough space for a small alley of negligible width between two neighbouring buildings.
Since you are already late for the contest start, you need to find a shortest path from your hotel to the contest site. Fortunately, you have a map of the city.
:::align{center}
:::
Figure: Illustration of Sample Input 1, with a shortest path shown in red.
输入格式
The input consists of:
One line with two integers and (), the number of rows and the number of columns of buildings shown on the map of the city.
lines, each with characters which are either O for round towers or X for square buildings, describing the shapes of the buildings.
The map is oriented with the north side up.
输出格式
Output the length of a shortest path from the north-west corner to the south-east corner of Delft in metres. Your answer may have a relative or absolute error of at most .
:::