ザグレブ市当局は新しい駐車場を建設することにしました。そのために、$N$ 行 $M$ 列の行列として表される長方形の土地を利用します。市長は、客を呼び込み収益を上げるため、あらかじめ決められた土地の区画に噴水、井戸、水飲み場などの施設を設置することにしました。残りの区画は車両の移動用として確保され、以下のいずれかの用途に整備されます。

• 駐車スペース
• 車両の自由移動用スペース

車両は、隣接する区画（北、南、東、西のいずれか）へ移動することで駐車場内を走行できます。駐車場は、どの時点においても、すべての駐車スペースから左上の区画（1行目1列目）にある入口/出口へ到達できるように建設されなければなりません。つまり、駐車中の車両が他の車両の出口を塞いではいけません。言い換えれば、駐車中のすべての車両は、他の駐車車両を移動させることなく駐車場から出られる必要があります。

市長を助け、与えられた土地に対して設置可能な駐車スペースの最大数を求めてください。

注記：1行目1列目の区画は駐車場の入口であり、駐車用ではないため、常に空いています。

入力

1行目に、土地の行数と列数を表す自然数 $N$ と $M$ ($1 \le N \le 6, 1 \le M \le 100$) が与えられます。 続く $N$ 行には、土地の様子を表す $M$ 文字の文字列が与えられます。

• 文字 'x' は噴水が設置される区画を表します。
• その他の区画は文字 '.' で表され、駐車場として整備されます。

出力

駐車スペースの最大数を1行に出力してください。

小課題

入出力例

入力 1

3 3
...
.x.
...

出力 1

2

入力 2

3 3
...
..x
...

出力 2

4

入力 3

3 6
.x..x.
..x.x.
......

出力 3

3

入力 4

4 5
....x
....x
..x..
.x..x

出力 4

7

注記

4番目の例の解説：駐車スペースの配置の一例：

.PPPx
....x
.Px.P
PxP.x