Minimum Cost Carrot Removal

You are given an \(n \times 2\) grid of carrots. Each cell \(a_{i,j}\) (with \(1 \le i \le n\) and \(j \in \{1,2\}\)) is either a white carrot (denoted by 0) or a red carrot (denoted by 1). You can perform two types of operations:

• Removal operation: With a cost of \(1\), choose any cell that currently contains a carrot and remove all carrots in its \(4\)-connected component (neighbors up, down, left, right) that have the same color. Afterwards, gravity acts: For every carrot at row \(i\) (\(i>1\)), if the cell directly above (row \(i-1\)) is empty, the carrot falls into that cell. This falling continues until each remaining carrot is supported (i.e. the cell immediately above it is non‐empty or it is in the first row).
• Shift operation: You may choose a column \(k\) (either 1 or 2) and shift all carrots in that column downward. Formally, for every \(r \ge 2\), the carrot in cell \(a_{r-1,k}\) moves to cell \(a_{r,k}\) (overwriting its previous contents), and a red carrot (i.e. value 1) is inserted into cell \(a_{1,k}\). The very first shift operation is free (cost \(0\)); all subsequent shift operations cost \(1\) each.

Your task is to remove all carrots from the grid (i.e. make every cell empty) with minimum total cost. If a cell is empty, we will represent it internally as \(-1\).

Note on indices and operations: The grid rows are numbered from 1 (top) to \(n\) (bottom). In the removal operation, gravity makes any unsupported carrot fall to the row immediately above (i.e. decreasing its row index) repeatedly until no such move is possible.

inputFormat

The first line contains an integer (n) (the number of rows). Each of the next (n) lines contains two space‐separated integers (either 0 or 1) representing the carrots in that row (from left to right).

outputFormat

Output a single integer denoting the minimum total cost required to remove all carrots from the grid.

sample

1
0 1

1