题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

2 3
#.#
###

3

4 3
.#.
###
.##
.#.

3

4 4
####
#.#.
#.##
####

5

数据范围与提示

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

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

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