Problem Description

There are $n\times 2$ carrots arranged in two columns. Carrots are either white or red. We use $a_{i,j}=0/1$ to represent whether the carrot in row $i$, column $j$ is white or red.

Each time, you may pay a cost of $1$ to choose a position that currently has a carrot, and remove all carrots in the 4-connected maximal connected component consisting of carrots of the same color as that chosen carrot. After that, if a carrot is in row $i$ and the corresponding position in row $i-1$ has no carrot, then it will fall to row $i-1$.

Also, you may pay a cost that is initially $0$ to choose $k=1/2$ and shift all carrots in column $k$ upward ($a_{i,k}\to a_{i+1,k}$), and place a red carrot, i.e. $1$, into row $1$, column $k$ ($1\to a_{1,k}$). After this, the cost of this operation increases by $1$ each time it is used.

Find the minimum total cost to remove all carrots.

Input Format

The first line contains a positive integer $n$, the number of rows of carrots.

The next $n$ lines each contain two integers, which are $a_{i,1},a_{i,2}$.

Output Format

Output one integer in one line, representing your answer.

4
0 1
0 1
0 1
0 1

2

6
1 0
1 0
0 1
0 1
1 0
1 0

3

Hint

For all test points, $a_{i,j}\in \{0,1\}$, $1\leq n\leq 5\times 10^6$, and it is guaranteed that $a_{i,1}\neq a_{i,2}$.

This problem uses bundled tests.
$\sf subtask \ 1: n\leq10 \ \ \ \ \ \ \ \ \ \ \ 30pts$
$\sf subtask \ 2: n\leq100 \ \ \ \ \ \ \ \ \ 20 pts$
$\sf subtask \ 3: n\leq5000 \ \ \ \ \ \ \ 20 pts$
$\sf subtask \ 4: n\leq5000000 \ 30pts$

Translated by ChatGPT 5