Description

An Advent calendar can be represented as a grid with $n$ rows and $m$ columns. Each cell contains a small window, and behind each window there is a piece of chocolate. Slavko has already opened some windows, while the others are still closed.

Mirko decides to use his tape to seal all closed windows. The tape has unlimited length, and its width fits exactly one window. Mirko can tear off a piece of tape to seal a consecutive segment of closed windows in one horizontal row or one vertical column. He does not want to put more than one piece of tape on any window, because he still wants to remain Slavko’s friend.

He wants to know the minimum number of tape pieces needed to seal all closed windows.

Input Format

The first line contains two integers $n, m$, which describe the size of the Advent calendar.

The next $n$ lines each contain $m$ characters, describing the cells of the calendar. . means an opened window, and # means a closed window.

Output Format

Output the minimum number of tape pieces needed to seal all closed windows.

2 3
#.#
###

3

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

3

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

5

Hint

[Sample Explanation #1]

One valid solution is to use tape on the entire first column, the entire third column, and the cell at row $2$, column $2$.

[Constraints]

For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le m \le 10$.

[Notes]

The scoring of this problem follows the original COCI problem, with a maximum of $110$ points.

Translated from COCI2020-2021 CONTEST #3 T4 Selotejp.

Translated by ChatGPT 5