Problem Background

In Mirko's view, nothing is more delightful than finding a new roll of tape, and today he is especially happy because he found Slavko's Advent calendar.

Problem Description

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

Mirko plans to use his tape to close all the windows. The tape is infinitely long and matches the width of a window. Mirko can tear off a piece of tape to close a continuous row or column of windows. He doesn't want to use too much tape because he still wants to be friends with Slavko.

He wants to know the minimum number of tapes required to close all the windows.

Input Format

The first line of input contains two integers $n$ and $m$, representing the dimensions of the Advent calendar.

The next $n$ lines each contain $m$ characters, representing the cells of the Advent calendar. . denotes a closed window, and # denotes an open window.

Output Format

Output the minimum number of tapes required to close all the windows.

Sample Input and Output

Sample Input #1

2 3
#.#
###

Sample Output #1

3

Sample Input #2

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

Sample Output #2

3

Sample Input #3

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

Sample Output #3

5

Notes/Hints

[Sample Explanation #1]

One valid solution: Use tape on the entire first column, the entire third column, and the second row at the second column.

[Data Range]

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

[Note]

This problem's score is set according to the original COCI contest, with a full score of $110$.

The problem is translated from COCI2020-2021 CONTEST #3 T4 Selotejp.

见题面 Input 部分

见题面 Output 部分