Maximal Block Removal in the Tower Corridor

In the tower corridor, the structure is represented by a grid of n rows and m columns. There are K blocks (each block is a collection of contiguous grid cells) stacked together to form the tower. The first row is the highest level and the n-th row is the floor.

Each block has a bottom layer defined as all the cells of that block with the maximum row index it occupies. Let the number of these cells be \(L\). A block is stable (i.e. will not fall) if and only if the contact area \(L'\) from its bottom layer with either the floor or the top faces of blocks underneath is at least \(\left\lceil \frac{L}{2} \right\rceil\). In our grid model a bottom cell is automatically supported if it is in row n (i.e. touching the floor) and if a bottom cell is not on the floor then its support comes only from the block occupying the cell immediately below; note that if the block below is the same block then it does not count.

Fuhua can shatter (i.e. remove) some of the blocks. However, after removal the tower must satisfy two conditions:

1. The tower does not collapse: every block that remains must be stable. For a block \(b\) with bottom layer length \(L_b\) (with all its bottom cells in the same row \(r_b\)), if \(r_b<n\) then the block is stable if and only if \[ \bigl(|\{ (r_b,c)\in b:\, r_b=n \text{ or } (r_b+1, c) \text{ is occupied by a block }\neq b\}|\bigr) \ge \left\lceil \frac{L_b}{2} \right\rceil. \] (For blocks whose bottom lies on row n, all cells are automatically supported by the floor and hence stable.)
2. The height of the tower does not change – that is, you cannot shatter all blocks that appear in the topmost row (row 1).

Initially the entire tower (all K blocks) is present and is stable. Fuhua wants to shatter as many blocks as possible without causing collapse and while keeping at least one block in the top row. Help Bronya determine the maximum number of blocks that can be shattered.

Note on the grid input: The tower is given as an n × m matrix where each cell contains a positive integer between 1 and K (inclusive) indicating the block ID occupying that cell.

inputFormat

The first line contains two integers n and m (n, m ≥ 1). The following n lines each contain m integers. The integer in the i-th row and j-th column (1-indexed) indicates the block ID (between 1 and K) that occupies that cell.

You may assume that the tower is completely filled by blocks and that every block appears at least once.

outputFormat

Output a single integer – the maximum number of blocks that can be shattered so that the remaining tower does not collapse and there is at least one block in the top (first) row.

sample

3 3
1 1 1
1 1 1
1 1 1

0