0423 - 画数

もんだい

'*'で描かれた図形を与えるのでその図形が最小何画で描けるのかを求めるプログラムを作ってください。
始点は角でも線の途中でも、どこからでも良いとし、斜めに書くことや一度書いたところに重ねて書くことは禁止とします。

入力

H W
S1
S2
.
.
.
Sh-1

出力

最小の画数

制約

1 <= h,w <= 20
1 <= 画数の最大 <= 50

入出力例

入力例1

5 5
*****
*...*
*...*
*...*
*****

出力例1

1

入力例2

5 7
****..*
*......
****..*
*.....*
****..*

出力例2

4

入力例3

5 5
*****
*.*.*
*****
*.*.*
*****

出力例3

3