Delft Distance

문제

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 $h\times wh\; \backslash times\; w$ 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 $10\text{m}10\; \backslash text\{m\}$ and all round towers have a diameter of $10\text{m}10\; \backslash text\{m\}$. 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. See Figure D.1 for an example.

Figure D.1: Illustration of Sample Input 1, with a shortest path shown in red.

입력

The input consists of:

• One line with two integers $hh$ and $ww$ ($1\le h,w\le 7001\; \backslash leq\; h,w\; \backslash leq\; 700$), the number of rows and the number of columns of buildings shown on the map of the city.
• $hh$ lines, each with $ww$ 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 ${10}^{-6}10^\{-6\}$.

3 5
XOOXO
OXOXO
XXXXO

71.4159265359

1 4
XOOX

45.7079632679