问题描述

Takahashi在一个由$H$行$W$列方块组成的溜冰场上。用$(r, c)$表示从北方算起的第$r$行、从西方算起的第$c$列的方块。每个方块要么是冰要么是地面；如果$S_{r, c}$是#，则$(r, c)$是地面；如果$S_{r, c}$是.，则$(r, c)$是冰。溜冰场四周是墙壁。

当Takahashi站在溜冰场上静止不动时，他可以开始向东、西、南或北移动。移动开始后，他将沿着同一方向继续移动，直到撞到墙壁或者站在一个非初始位置的地面方块上。

我们说溜冰场对于$(r, c)$是高效的，当满足以下条件时：

• 有一系列的移动，从$(r, c)$开始静止，经过每个方块。（不需要在每个方块上停下来。）

Takahashi想要改变一些冰方块为地面方块，使得对于每个方块，溜冰场都是高效的。他至少需要改变多少个方块？

约束条件

• $2 \leq H, W \leq 1000$
• $S_{r,c}$ 是 # 或 .。

输入

输入以以下格式从标准输入给出：

$H$ $W$ $S_{1,1} \dots S_{1,W}$ $\vdots$ $S_{H,1} \dots S_{H,W}$

输出

输出改变溜冰场使得对于每个方块都是高效的所需的最小改变次数。

示例输入 1

3 9
.........
.........
.........

示例输出 1

1

初始状态下，从$(1,1)$开始到达$(2,2)$是不可能的。一种满足要求的方法是将溜冰场改变如下：

.........
........#
.........

示例输入 2

10 10
..........
#...#.....
..........
..........
..........
....#.....
.#......#.
..........
..........
..........

示例输出 2

6