Region Coloring

Interview

Time limit1sMemory limit512 MB

Summary

Given a grid of 0, 1, and 2 cells, find the fewest horizontal strokes that reproduce the picture, where strokes may overpaint but never cover a 0 cell.

Level: Medium5 of 10
Topics: Greedy, Array
Solved: No attempts yet

Problem

Sanjini tries to copy a given picture onto an empty grid sheet, following the grid lines. The picture uses two colors.

The brush can paint only in the horizontal direction, and its width is 1 cell. A single stroke can be any length, and painting over an area that is already painted is allowed.

Find the minimum number of brush strokes Sanjini needs to copy the picture exactly.

Input

The first line contains two integers $N$ and $M$ , separated by a space, the number of rows and the number of columns of the picture. $(2\leq N,M\leq 100)$

Each of the next $N$ lines contains $M$ integers separated by spaces. Each integer describes one cell. '0' means the cell is not painted, and '1' and '2' mean the cell is painted with that color.

Output

Print the minimum number of brush strokes needed to copy the picture exactly.

Examples2

Example 1
Input
```
2 2
2 1
0 0
```
Expected output
```
2
```
Example 2
Input
```
4 4
1 0 0 1
1 1 2 2
0 0 1 2
0 1 1 1
```
Expected output
```
7
```