题目描述

译自 COCI 2020/2021 Contest #3 T4. Selotejp

没有什么能比找到一卷新的胶带更令 Mirko 快乐。今天他格外开心，因为他还找到了 Slavko 的圣诞日历。

圣诞日历可以被表示为一个 $n$ 行，$m$ 列的表格。每个格子里有一个正方形的窗口，窗口里面有巧克力。Slavko 已经打开了一些窗口并吃掉了巧克力，还剩余一些窗口没有被打开。

Mirko 准备用他的胶带覆盖所有关闭的窗户。Mirko 可以获得任意长度的胶带，而所有胶带纸的宽度都与窗口的长度相同。Mirko 可以用一卷胶带横向或纵向覆盖一排关闭的窗口，胶带中途不能经过打开的窗口。为了不让 Slavko 过于生气，一个窗口不能被两卷或以上胶带覆盖。

Mirko 想要知道，如果他想把所有关闭的窗口都覆盖，至少需要多少卷胶带呢？

输入格式

第一行包含两个整数 $n, m$。

接下来 $n$ 行，每行有 $m$ 个字符，表示圣诞日历每一个窗口的状态，. 表示打开，而 # 表示关闭。

输出格式

输出一行一个整数，表示关闭所有窗口至少需要的胶带数量。

样例 1

输入 2 3 #.#

text

输出 3

text

我们可以分别在第一列一整列、第三列一整列和第二行第二列处使用胶带从而得到一种方案。

样例 2

输入 4 3 .#.

.## .#.

text

输出 3

text

样例 3

输入 4 4

#.#. #.##

text

输出 5

text

数据范围与提示

对于所有子任务，保证 $1 \le n \le 1000$，$1 \le m \le 10$。

详细子任务附加限制与分值如下表：

子任务	附加限制	分值
1	每个关闭的窗口至多与两个关闭的窗口相邻	$10/110$
2	$1 \le n,m \le 300$	$40/110$
3	无附加限制	$60/110$

这里的相邻指存在一条两个方格共享的边。