AT_xmascon19_f Stamps 1

[problemUrl]: https://atcoder.jp/contests/xmascon19/tasks/xmascon19_f うさぎは $ H\ \times\ W $ の長方形のマス目を持っている． マス目の上から $ i $ 行目 ($ 1\ \le\ i\ \le\ H $)，左から $ j $ 列目 ($ 1\ \le\ j\ \le\ W $) のマスをマス $ (i,j) $ と呼ぶ． マス $ (i,j) $ の初期状態は文字 $ S_{i,j} $ で表され，`#` は黒く塗られていること，`.` は塗られていないことを意味する． うさぎはクリスマスプレゼントとしてスタンプをもらった． このスタンプを $ 1 $ 回押すと縦 $ H/2 $ マス横 $ W/2 $ マスの大きさの長方形を黒く塗りつぶすことができる． すなわち，整数 $ i_0,j_0 $ を選んだとき，$ i_0\ \le\ i\ \lt\ i_0+H/2 $ かつ $ j_0\ \le\ j\ \lt\ j_0+W/2 $ を満たすようなマス $ (i,j) $ を全て黒く塗ることができる． うさぎはこのスタンプを使って全てのマスを黒く塗ろうとしている． 最小で何回スタンプを押せば良いだろうか？

入力は以下の形式で標準入力から与えられる． > $ H $ $ W $ $ S_{1,1} $$ S_{1,2} $$ ... $$ S_{1,W} $ $ S_{2,1} $$ S_{2,2} $$ ... $$ S_{2,W} $ $ : $ $ S_{H,1} $$ S_{H,2} $$ ... $$ S_{H,W} $

全てのマスが黒く塗られた状態にするためにスタンプを押す必要のある回数の最小値を出力せよ．

### 制約 - $ 2\ \le\ H,W\ \le\ 1000 $ - $ H,W $ はいずれも偶数 - $ S_{i,j} $ は `.` または `#` ### Sample Explanation 1 例えば，下図の通りに押すと $ 3 $ 回で全てのマスを黒く塗ることができる． !\[b50ca03a62fb58d6362e2ea94e6d1e7d.png\](https://img.atcoder.jp/xmascon19/b50ca03a62fb58d6362e2ea94e6d1e7d.png)