cho.sh

Painting the Board

Given a grid picture of black and white squares, find the minimum number of horizontal or vertical strokes that paint exactly the required black squares.

Medium6Dynamic programmingGreedyMatrixNo attempts yetTime limit2sMemory limit512 MB

Problem

A rectangular board is divided into unit squares. Every square is white at the start. You want to paint some of the squares black so that the board matches a given picture.

One painting operation picks consecutive white squares inside a single row or a single column and paints all of them black. Every picked square has to be white at that moment. A stroke therefore cannot run across a square that is already black, and it cannot touch a square that has to stay white.

Write a program that finds the smallest number of painting operations needed to produce the picture.

Input

The first line contains the height NN and the width MM of the board (1≤N,M≤501 \le N, M \le 50).

Each of the next NN lines contains MM characters. A '.' is a square that has to stay white, and a '#' is a square that has to be painted black.

Output

Print the smallest number of painting operations. If no square has to be painted, print 0.