20510번 - Selotejp 서브태스크다국어

For Mirko there is no greater happiness than finding a new roll of sticky tape, and today he is especially happy because he had also found Slavko’s Advent calendar.

The Advent calendar can be represented as a table with n rows and m columns. Each square contains a little window, and behind each window is a piece of chocolate. Slavko had already opened some of the windows, and others are still closed.

Mirko decided to use his sticky tape to glue all closed windows shut. The tape is infinitely long, and it is one calendar cell wide. Mirko can rip off a piece of tape and use it to glue some sequence of horizontally or vertically adjacent closed windows shut. He doesn’t want to put more than one piece of tape over some window, since he wants to remain friends with Slavko.

He is wondering what is the minimal number of pieces of tape he needs to glue all closed windows shut.

The first line contains integers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10), dimensions of the Advent calendar.

Each of the following n lines contains m characters '.' and '#' that represent the Advent calendar. The character '.' denotes an open window, and the character '#' denotes a closed window.

Output the minimal number of pieces of tape needed to glue all closed windows shut.

Clarification of the first example:

One possible solution is to use one piece of tape for the first column, one piece for the third column, and one piece for the window in the second row and second column.