Carrot Harvest Optimization

You are given a 2 \(\times n\) grid representing two rows of carrots. Each cell contains a carrot which is either a white carrot or a red carrot. The color is represented by a binary value \(a_{i,j}\) where \(a_{i,j}=0\) means the carrot is white and \(a_{i,j}=1\) means it is red. (Here the columns are indexed from \(1\) to \(n\) and the rows are the first (top) and the second (bottom)).

You are allowed to perform the following operation any number of times: choose any cell (which still contains a carrot) and remove the entire 4-connected component of carrots of the same color that contains that cell. Two carrots are 4-connected if they share a side (up, down, left, or right).

Note: After an operation, for any column, if the carrot in the second row (bottom) remains while the corresponding cell in the first row (top) is empty, then the carrot in the second row will fall upward into the first row.

Your task is to remove all the carrots at minimum total cost. Each operation costs \(1\) unit. Find the minimum cost required.

Hint: Because the grid has only two rows, after a proper sequence of operations, every column eventually contributes at most one removal block. In particular, consider that if the two carrots in a column are of the same color (a unified column), they obviously form one block (cost \(1\)). If they are of different colors (a split column), then no matter the order of removals, you have to remove two blocks (total cost \(2\)) if done independently. However, careful ordering may allow blocks in adjacent columns to merge (if their final surviving carrot after gravity has the same color) thus reducing the overall cost. One may show that the minimum cost is given by

[ \text{Answer} = \Big((#\text{unified}) \times 1 + (#\text{split}) \times 2\Big) - \text{(maximum number of merges between adjacent columns)}. ]

For each split column (where the top and bottom carrots differ), you have a choice: you can either remove the top carrot first (letting the bottom fall, making the final column color equal to the bottom carrot) or remove the bottom carrot first (leaving the top as the final carrot). Unified columns have no such choice. By appropriately making these choices column‐by‐column, you can maximize the number of merges between adjacent columns (a merge is possible if the final colors in two adjacent columns are the same) and hence minimize the overall cost.

Solve for the minimum cost.

inputFormat

The first line contains a positive integer \(n\) (the number of columns).

The next two lines each contain a string of \(n\) characters. The first of these lines represents the first (top) row, and the second represents the second (bottom) row. Each character is either 0 (white carrot) or 1 (red carrot).

outputFormat

Output a single integer: the minimum cost required to remove all carrots.

sample

1
0
0

1