最先端を司る神 NASURA は、情報科学・バイオサイエンス・物質創成科学の領域をそれぞれ専門とする $3$ つの頭を持っています。
NASURA は分身して $H \times W$ のグリッド状の迷宮を監視することになりました。 グリッドの上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と表します。
グリッドの各マスは空きマスまたは壁マスのいずれかです。
各マスの情報は $H$ 個の長さ $W$ の文字列 $S_1,S_2,\dots,S_H$ で与えられ、$S_i$ の $j$ 文字目が . のときマス $(i,j)$ は空きマス、$S_i$ の $j$ 文字目が # のときマス $(i,j)$ は壁マスです。
あなたは、いくつかの空きマスに NASURA を配置します。$1$ 体の NASURA は、以下の範囲を同時に監視することができます。
$4$ 方向のうち、どの $1$ 方向を死角（頭が向いていない方向）とするかは、配置する NASURA ごとに自由に決めることができます。ひとつのマスに配置できる NASURA は $1$ 体までです。
すべての空きマスを $1$ 体以上の NASURA で監視するために必要な、NASURA の最小個数を求めてください。
.,# からなる長さ $W$ の文字列入力は以下の形式で標準入力から与えられます。
$H$ $W$ $S_1$ $\vdots$ $S_H$
答えを出力してください。
3 3 .#. ... .#.
2
例えば、以下のように配置します。 (⊢は死角が左方向の NASURA を、⊥は死角が下方向の NASURA を表します)。
.#. ⊢.. .#⊥
マス $(2,1)$ にある NASURA は以下の@のマスを監視できます。
@#. @@@ @#.
マス $(3,3)$ にある NASURA は以下の@のマスを監視できます。
.#@ ..@ .#@
よって、$2$ 体の NASURA ですべての空きマスを監視できます。 $2$ 体未満の NASURA ですべての空きマスを監視することはできません。
2 30 ....##.#....#...#.#..#...#.... ..#....#..#...#....#...#.#..#.
13