配点: 4 点
問題文
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 存在一个以上
入力
输入是按以下格式从标准输入给出的。
H W
c_{1,1} c_{1,2} \cdots c_{1,W}
c_{2,1} c_{2,2} \cdots c_{2,W}
\vdots
c_{H,1} c_{H,2} \cdots c_{H,W}
出力
请输出铁路线路经过的格子数的最大值。
如果不存在符合条件的铁路线路,请改为输出 -1 请输出。
入力例 1
3 3 ... .#. ...
出力例 1
8
例如,以下铁路线路经过 8 个格子。

入力例 2
1 6 ......
出力例 2
-1
由于不存在符合条件的铁路线路,-1 可以输出这个。
入力例 3
4 4 .... #... .... ...#
出力例 3
12
例如,以下铁路线路经过 12 个格子。
