Optimal Paper Cutting

Paper‐cutting is one of China’s oldest folk arts. Traditionally the paper is folded along a horizontal or vertical line – always along a line between two rows or two columns – and then cut. In a typical masterpiece the paper is folded one or more times and, with a single snip of the scissors, an entire connected component (possibly hidden within layers) is removed. Note that two 1×1 blocks are connected if they share an edge.

You are given the final appearance of the paper as an n×m matrix of 0’s and 1’s. A 0 indicates a removed (cut‐out) block while a 1 indicates a block left intact. Before cutting, you are allowed to fold the paper any number of times (possibly zero) according to the following rules:

• Choose a vertical line between two columns or a horizontal line between two rows. This line splits the paper into two parts.
• Fold the smaller side of the paper onto the larger side over the chosen axis. (If both sides have equal size, you may choose either side to fold.)

The folding process overlays several blocks; however, you are only allowed to use the scissors if, after folding, each stack (that is, each position in the folded paper) is homogeneous (all 0’s or all 1’s). In one scissor cut you can remove one connected component (by 4‐direction adjacency) of stacked 0’s from the folded paper. Once removed, when the paper is unfolded the corresponding positions will be missing.

Your task is to determine the minimum number of scissor cuts required, assuming you can choose an optimal sequence of folds so that the cutting process is as efficient as possible.

Note: It is always allowed to perform no folds. In that case, you simply cut the 0’s as they appear (each connected region requiring a separate cut).

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 8) representing the dimensions of the paper.

Then follow n lines, each containing m integers (each either 0 or 1) separated by spaces, representing the final picture of the paper.

outputFormat

Output a single integer which is the minimum number of scissor cuts required.

sample

2 2
1 0
0 1

2