Painting roofs

Interview

Time limit1sMemory limit256 MB

Summary

Given a grid of two colors, recolor the fewest cells so that the grid becomes bipartite by parity, i.e. every side-adjacent pair differs.

Level: Medium6 of 10
Topics: Graph, Matrix, Greedy, Implementation
Solved: No attempts yet

Problem

The King of Berland loves order in everything. For instance, the capital of Berland as seen on the map is a rectangular field of cells, which correspond to city quarters.

He recently issued a decree stating that all roofs in a quarter must be painted the same color, either red or blue. The capital of Berland is expecting a commission that will check the whole city for compliance, moving from one quarter to a quarter adjacent by a side. For a successful check, the commission must be able to reach any quarter from any other.

The Minister of Finance found out that the commission has a curious demand. They cannot move to an adjacent quarter if its roofs have the same color as the roofs of the quarter they are currently in. Consequently, some quarters will have to repaint all their roofs to pass the check. The Minister of Finance wants to save money. He asks you to find the minimal number of quarters where all roofs must be repainted.

Input

The first line of the input file contains two integers $m$ and $n$ , the number of rows and columns in the city map ( $1\le m, n\le 1000$ ). The next $m$ lines consist of $n$ symbols, each symbol being either '1' or '2'. The symbol '1' means that all roofs in the corresponding quarter are blue, and the symbol '2' means that the roofs are red.

Output

Print a single integer: the minimal number of quarters where the roofs must be repainted.

Examples1

Example 1
Input
```
1 4
2211
```
Expected output
```
2
```