AT_soundhound2018_c 広告

[problemUrl]: https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c 縦に $ r $ 個、横に $ c $ 個の $ r×c $ 個のマスからなるグリッドがあり、それぞれのマスには `*` か `.` が書かれています。上から $ i $ 番目、左から $ j $ 番目のマスに書かれた文字を $ C_{i,j} $ とおきます。 kenkooooさんは `.` のマスにSoundHoundの広告を打つことにしました。$ 1 $ つのマスには $ 1 $ 個だけ広告を打てます。しかし、あまりに密集していると逆効果なので、隣り合う $ 2 $ つのマスの両方に広告を打つことはありません。ここで、隣り合う $ 2 $ つのマスとは、あるマスとその上下左右で隣り合うマスのことを表します。 kenkooooさんは最大でいくつ広告を打てるでしょうか？

入力は以下の形式で標準入力から与えられる。 > $ r $ $ c $ $ C_{1,1} $$ C_{1,2} $ $ ... $ $ C_{1,c} $ $ : $ $ C_{r,1} $$ C_{r,2} $ $ ... $ $ C_{r,c} $

kenkooooさんが最大で打てる広告の数を出力してください。

### 制約 - $ 1≦r,\ c≦40 $ - $ C_{i,j} $ は `.` または `*` からなる ### Sample Explanation 1 広告を打つマスを `#` で表すことにすると、以下のように $ 5 $ つの広告を打つことができます。 ``` #.# .#. #.# ``` ### Sample Explanation 2 残念ながら、$ 1 $ つも広告を打てないときもあります。