Chocolate

Dory and Wendy have a chocolate bar with dark, white and mixed chocolate cubes. Dory likes dark chocolate and Wendy likes white chocolate. The girls want to divide the chocolate so that Dory receives all the dark cubes while Wendy receives all the white cubes. They do not care about the mixed cubes so it does not matter how many mixed cubes Dory or Wendy gets. The chocolate bar is divided in the usual way. A bar can be broken vertically or horizontally into two pieces along a line between two neighboring rows or columns of chocolate cubes. Each of the pieces is again a rectangular bar. The process of division is then repeatedly applied to chosen pieces. The girls want to find an optimal division which separates dark and white cubes and produces the smallest possible number of pieces. Two examples of such optimal divisions are shown in Image 1 and Image 2.



Image 1. a) A chocolate bar of size 3 × 3. b) An optimal separation of dark and white cubes, which consists of 3 pieces.



Image 2. a) A chocolate bar of size 4 × 4. b) An optimal separation of dark and white cubes, which consists of 7 pieces.

The task

Given a layout of a chocolate bar, find an optimal division which separates dark and white cubes and results in the smallest possible number of pieces.


Input

The first input line contains two integers M, N separated by space. The first integer is the number of chocolate bar rows, while the second integer is the number of its columns. M lines representing rows of the chocolate bar follow. Each line contains N integers separated by spaces. The j-th integer in i-th line represents the chocolate cube located in the i-th row and j-th column. The integer is a value from {0,1,2} where 0 indicates a dark cube, 1 indicates a white cube and 2 indicates a mixed cube. It holds 1 ≤ M, N ≤ 50.

Output

The output consists of one line containing one integer which corresponds to the minimal number pieces to which the chocolate bar must be divided to separate dark and white cubes.

Example 1

Input
3 3
1 1 2
1 2 0
2 0 0
Output
3
Example 2 is visualized in Image 1.

Example 2

Input
4 4
0 1 1 1
1 0 1 0
1 0 1 0
2 0 0 0
Output
7
Example 2 is visualized in Image 2.

Example 3

Input
5 8
0 1 0 1 0 1 0 2
1 0 2 0 2 0 1 0
0 2 0 2 0 1 0 2
1 0 2 0 2 0 1 0
0 1 0 1 0 1 0 2
Output
24

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set