Canal

Problem Statement

The Kingdom of JOIG is a rectangle divided into a grid of H rows and W columns. The cell in the i-th row from the top (1 ≦ i ≦ H) and the j-th column from the left (1 ≦ j ≦ W) is called cell (i,j).

Each cell has an integer called its elevation. The elevation of cell (i,j) is A_i,j.

The Kingdom of JOIG has decided to build a canal that runs vertically across the kingdom. The canal is constructed as follows.

• Choose an integer k (1 ≦ k < W). Build a canal that runs from the top edge to the bottom edge of the kingdom, between the k-th column from the left and the k+1-th column from the left.

A set of cells that are mutually reachable by repeatedly moving to adjacent cells (sharing an edge) with the same elevation, without crossing the canal, is called a plain. To make the territory easier to manage, the position of the canal should be chosen so that the number of plains is as small as possible.

Given the topographical information of the Kingdom of JOIG, write a program that finds the minimum possible number of plains in the kingdom after the canal is built.

Constraints

• H ≧ 1.
• W ≧ 2.
• H × W ≦ 500000.
• 1 ≦ A_i,j ≦ 10⁹ (1 ≦ i ≦ H, 1 ≦ j ≦ W).
• All input values are integers.

Input

The input is given in the following format.
H W
A_1,1 A_1,2 … A_1,W
A_2,1 A_2,2 … A_2,W
:
A_H,1 A_H,2 … A_H,W

Output

Output the minimum possible number of plains in the Kingdom of JOIG after the canal is built.

Sample Input and Output

Sample Input 1

4 4
1 1 1 3
2 2 1 3
2 1 1 3
2 2 2 2

Sample Output 1

4

If the canal is built with k=3, the Kingdom of JOIG is divided into 4 plains as follows.

• A plain consisting of cells (1,1), (1,2), (1,3), (2,3), (3,2), and (3,3)
• A plain consisting of cells (2,1), (2,2), (3,1), (4,1), (4,2), and (4,3)
• A plain consisting of cells (1,4), (2,4), and (3,4)
• A plain consisting of cell (4,4)

It is impossible to reduce the number of plains in the Kingdom of JOIG to 3 or fewer, so output 4.

Sample Input 2

5 8
1 2 2 5 5 5 5 5
1 1 2 2 5 6 5 6
1 1 1 1 6 6 5 6
1 1 3 1 1 6 7 6
1 4 1 1 1 6 6 6

Sample Output 2

8

If the canal is built with k=1, the Kingdom of JOIG is divided into 8 plains. It is impossible to reduce the number of plains in the Kingdom of JOIG to 7 or fewer, so output 8.

Sample Input 3

1 6
1 1 2 2 3 3

Sample Output 3

3

Sample Input 4

2 10
1 1 1 1 1 3 3 3 3 4
1 2 1 3 3 3 1 1 3 3

Sample Output 4

6

---