問題文

ABC 王国は H 行 W 列のマス目であらわされます。各マスは山のマスと平野のマスのどちらかです。上から i 行目、左から j 列目にあるマスが山のマスなら c_{i,j} は # 、平野のマスなら c_{i,j} は . です。

あなたは鉄道路線を作りたいです。鉄道路線の経路は、以下の条件をすべて満たす必要があります。

条件1　あるマスを始点とし、辺を共有して隣接するマスに移動することを k 回 (3 \le k) 繰り返し、始点で終わる経路である。
条件2　k 回の移動について、移動先は相異なる。（始点と終点は一致してよい）
条件3　山のマスを通らない。

例えば左から 1 番目の鉄道路線は条件を満たしますが、左から 2, 3, 4, 5 番目の鉄道路線は条件を満たしません。

鉄道路線が通るマスの数としてあり得る最大値を求めてください。ただし、条件を満たす鉄道路線がない場合は、代わりにそれを報告してください。

制約

• H, W は正整数
• H \times W \leq 16
• c_{i,j} は # または .
• c_{i,j} が . である i,j (1 \leq i \leq H,1 \leq j \leq W) が 1 つ以上存在する

入力例 1

3 3
...
.#.
...

出力例 1

8

例えば、以下の鉄道路線は 8 個のマスを通ります。

入力例 2

1 6
......

出力例 2

-1

条件を満たす鉄道路線は存在しないため、-1 と出力すればよいです。

入力例 3

4 4
....
#...
....
...#

出力例 3

12

例えば、以下の鉄道路線は 12 個のマスを通ります。