Python言語で提出する際の諸注意

• この問題においてPython言語で解く際は、必ず入力の後に strip 関数を適用してください。
  つまり文字列の入力の際に input().strip() と書いてください（でないとジャッジの環境上、WAになる可能性があります）

Story

🍪

2年前か3年前か...
どこかのもふもふうさぎ界隈では、クッキーが話題になっていたようです。ラテ君はそれを思い出して、クッキーが食べたくなったようです。

おや、ちょうどあそこに新品のクッキーが落ちてますね。
そこで、道の掃除ついでにクッキーを拾っていくことにしたようです。ある意味お金持ちですね :)

問題

縦 $H$ マス、横 $W$ マスのマス目状の盤面 $A$ が与えられます。
$A$ は #, . , o からなり、# は壁マス、. は道マス、o はクッキーマスです。クッキーマスは道マスの一種としてみなされます。
ここで上から $i\ (1\le i\le H)$ 番目、左から $j\ (1\le j\le W)$ 番目のマスをマス $(i,j)$ と表すことにします。

今、ラテ君は $(1,1)$ に立っており、道マス(クッキーマスを含む)のみを通って $(H,W)$ にたどり着きたいと思っています。
この時ラテ君は上下左右の移動をすることができ、斜めには移動できません。

ラテ君はクッキーが食べたくて仕方ありません。
なので $(H,W)$ にたどり着く前に必ずすべてのクッキーを食べてから移動しようと思っています。ここで一度通ったマスに再度通っても構いません。

ただしクッキーマスが一つも存在しない場合は、ラテ君は寄り道をせずそのまま $(H,W)$ に移動します。

このとき、ラテ君は少なくとも何マス分の移動を行う必要がありますか？
ただしすべてのクッキーを拾うことができない場合は、その旨を報告してください。

入力

入力は以下の形式で与えられる。

制約

• $2\le H,W\le 500$
• $A_{i,j}$ は # . o からなる
• $A_{i,j}$ に含まれる o の個数は $15$ 以下
• $A_{1,1}=A_{H,W}=$ .

出力

答えを整数で出力せよ。
ただしどのように移動しても、すべてのクッキーを拾いながら $(H,W)$ にたどり着けないなら -1 を出力せよ。

入出力例

4 5
.#o.#
..#..
#...#
#.#..

13

クッキーマスは $(1,3)$ です。例えば次のように行動することで計 $13$ マス分の移動でたどり着くことができます。

• $(1,1)\to (2,1)\to (2,2)\to (3,2)\to (3,3)\to (3,4)\to (2,4)\to (1,4)\to (1,3)$ と移動し、クッキーを食べる
• $(1,3)\to (1,4)\to (2,4)\to (3,4)\to (4,4)\to (4,5)$ と移動する

$12$ マス分以下の移動で目標を達成することはできないので、$13$ が答えとなります。

3 3
.#o
.##
o..

-1

$(3,1)$ にあるクッキーを拾いながら $(H,W)=(3,3)$ へ移動することはできますが、$(1,1)$ にあるクッキーは拾うことができません。

2 2
.o
o.

4