問題文

HH マス,横 WW マスの H×WH \times W マスからなるグリッドで表されるダンジョンがあります.
上から ii 行目,左から jj 列目のマス (i,j)(i,j) は,Gi,jG_{i,j}# のときであり,. のときです.

このダンジョンの主である MojaMoja 君は,次の条件を満たすように,11 組の 22 マスを結ぶワープホールを非負整数個設置します.

条件

  • 任意の道のマスにいる人が,00 回以上の移動を繰り返すことによって,任意の道のマスへ到達することができる.

ここで,ある道のマス PP にいる人が,ある道のマス QQ へ移動できるとき,22 マス P,QP, Q は以下の条件のうち 11 つ以上を満たします.

  • P(i,j)P \eqqcolon (i, j) とするとき,Q{(i+1,j),(i1,j),(i,j+1),(i,j1)}Q \in \{(i+1,j), (i-1,j), (i,j+1), (i,j-1)\}
  • 11 組の 22 マス (P,Q)(P, Q) または (Q,P)(Q, P) を結ぶワープホールが存在する

MojaMoja 君が条件を満たすために,最小で何組のワープホールを設置する必要があるか,求めてください.

制約

  • 1H,W25001 \leq H,W \leq 2500
  • Gi,jG_{i,j}.# のうちのいずれか (1iH,1jW)\scriptsize (1 \leq i \leq H, 1 \leq j \leq W)

入力

入力は以下の形式で標準入力から与えられる.

HWH \hspace{0.5em} W
G1,1G1,2G1,WG_{1,1}G_{1,2}{\ldots}G_{1,W}
G2,1G2,2G2,WG_{2,1}G_{2,2}{\ldots}G_{2,W}
\vdots
GH,1GH,2GH,WG_{H,1}G_{H,2}{\ldots}G_{H,W}

出力

答えを出力せよ.

サンプル

入力例1
4 5
#.##.
#..##
#####
#..##
出力例1
2

たとえば,道のマスの組 ((2,3),(1,5))((2, 3), (1, 5)) を結ぶワープホールと,((2,2),(4,2))((2, 2), (4, 2)) を結ぶワープホールとを設置することで条件を満たします.
22 つ未満のワープホールによって目標を達成することはできないため,2 を出力します.


入力例2
4 5
#.#..
...##
.##..
#....
出力例2
2

入力例3
2 4
#.#.
.#.#
出力例3
3

提出


Go (1.21)