题目描述

有一个网格，从上到下有 $H$ 行，从左到右有 $W$ 列。用 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。
如果方格 $(i, j)$ 被障碍物占据，则 $S_{i,j}=$ #，否则为 .。

Takahashi 将在网格中安装一些监视摄像头。

监视摄像头可以放置在没有障碍物的方格中，可以朝四个方向之一放置：上、下、左、右。
同一个方格中可以放置多个监视摄像头。

每个监视摄像头监视它所放置的方格以及该方向上的方格，只要两者之间没有障碍物。

至少需要多少个监视摄像头才能监视所有没有障碍物的方格？

约束条件

• $1 \leq H,W \leq 300$
• $S_{i,j}$ 是 . 或 #。

输入

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

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

输出

输出答案。

示例输入 1

3 3
...
.#.
...

示例输出 1

4

例如，如果我们在方格 $(1, 1)$ 安装两个朝右和向下的监视摄像头，以及在方格 $(3, 3)$ 放置朝上和向左的另外两个监视摄像头，就能够监视所有没有障碍物的方格。

示例输入 2

3 5
...##
.#...
...#.

示例输出 2

5

例如，如果我们在方格 $(1, 1)$ 安装一个朝右和向下的监视摄像头，在方格 $(3, 3)$ 安装一个朝左的监视摄像头，以及在方格 $(2, 5)$ 安装两个朝左和向下的监视摄像头，就能够监视所有没有障碍物的方格。

请注意，方格 $(2, 5)$ 上面朝左的摄像头不能监视到方格 $(2, 1)$，因为中间有方格 $(2, 2)$ 上的障碍物。

示例输入 3

14 107
...........................................................................................................
...........................................................................................................
..#########..###....###########..###.......###...###########..####.......###...###########...###########...
..########..###....###########....###.....###...###########...#####......###..###########...###########....
..#######..###.....###.............###...###....###...........######.....###..###...........###............
..######..###......###..............###.###.....###...........###.###....###..###...........###............
..#####..###.......############......#####......############..###..###...###..###...........############...
..####....###......############.......###.......############..###...###..###..###...........############...
..###......###.....###................###.......###...........###....###.###..###...........###............
..##........###....###................###.......###...........###.....######..###...........###............
..#..........###...############.......###.......############..###......#####..############..############...
..............###...###########.......###........###########..###.......####...###########...###########...
...........................................................................................................
...........................................................................................................

示例输出 3

91