CF1739E.Cleaning Robot

Consider a hallway, which can be represented as the matrix with $2$ rows and $n$ columns. Let's denote the cell on the intersection of the $i$-th row and the $j$-th column as $(i, j)$. The distance between the cells $(i_1, j_1)$ and $(i_2, j_2)$ is $|i_1 - i_2| + |j_1 - j_2|$.

There is a cleaning robot in the cell $(1, 1)$. Some cells of the hallway are clean, other cells are dirty (the cell with the robot is clean). You want to clean the hallway, so you are going to launch the robot to do this.

After the robot is launched, it works as follows. While at least one cell is dirty, the robot chooses the closest (to its current cell) cell among those which are dirty, moves there and cleans it (so the cell is no longer dirty). After cleaning a cell, the robot again finds the closest dirty cell to its current cell, and so on. This process repeats until the whole hallway is clean.

However, there is a critical bug in the robot's program. If at some moment, there are multiple closest (to the robot's current position) dirty cells, the robot malfunctions.

You want to clean the hallway in such a way that the robot doesn't malfunction. Before launching the robot, you can clean some (possibly zero) of the dirty cells yourself. However, you don't want to do too much dirty work yourself while you have this nice, smart (yet buggy) robot to do this. Note that you cannot make a clean cell dirty.

Calculate the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn't malfunction.

考虑一条走廊，它可以表示为一个 $2$ 行 $n$ 列的矩阵。我们用 $(i, j)$ 表示第 $i$ 行与第 $j$ 列相交的格子。格子 $(i_1, j_1)$ 与 $(i_2, j_2)$ 之间的距离定义为 $|i_1 - i_2| + |j_1 - j_2|$。

清洁机器人初始位于格子 $(1, 1)$。走廊中部分格子已清洁，其余格子为脏（含机器人的起始格子 $(1, 1)$ 本身也为清洁状态）。你的目标是清洁整条走廊，因此你将启动该机器人来完成此项任务。

机器人启动后按如下方式工作：只要至少存在一个脏格子，机器人就会在所有脏格子中选择距离其当前所在格子最近的一个，移动至该格子并将其清洁（此后该格子不再为脏）。清洁完毕后，机器人再次以其当前位置为基准，寻找最近的脏格子，依此类推。该过程持续进行，直至整条走廊全部清洁完毕。

然而，机器人程序中存在一个严重缺陷：若在某一时刻，存在多个与机器人当前位置距离相等（即均为最近）的脏格子，则机器人将发生故障。

你希望以一种不会导致机器人故障的方式清洁走廊。在启动机器人之前，你可以手动清洁若干个（可能为零个）脏格子。但你不希望亲自动手清洁太多——毕竟你拥有这个先进、智能（尽管有缺陷）的机器人来代劳。注意：你不能将已清洁的格子重新弄脏。

请计算：在保证机器人不发生故障的前提下，你最多可以保留多少个脏格子（即在启动机器人前，最少需手动清洁多少个脏格子）？

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of columns in the hallway.

Then two lines follow, denoting the $1$-st and the $2$-nd row of the hallway. These lines contain $n$ characters each, where 0 denotes a clean cell and 1 denotes a dirty cell. The starting cell of the robot $(1, 1)$ is clean.

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 表示走廊中的列数。

接下来是两行，分别表示走廊的第 $1$ 行和第 $2$ 行。每行包含 $n$ 个字符，其中 0 表示干净的格子，1 表示脏的格子。机器人起始位置 $(1, 1)$ 是干净的。

Print one integer — the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn't malfunction.

输出一个整数——在启动机器人之前，你可以让其保持脏污状态的最大可能格子数量，使得机器人不会发生故障。

In the first example, you can clean the cell $(1, 2)$, so the path of the robot is $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$.

In the second example, you can leave the hallway as it is, so the path of the robot is $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$.

In the third example, you can clean the cell $(1, 2)$, so the path of the robot is $(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$.

In the fourth example, the hallway is already clean. Maybe you have launched the robot earlier?

在第一个例子中，你可以清理单元格 $(1, 2)$，因此机器人的路径为 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$。

在第二个例子中，你可以保持走廊原样不变，因此机器人的路径为 $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$。

在第三个例子中，你可以清理单元格 $(1, 2)$，因此机器人的路径为 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$。

在第四个例子中，走廊已经清洁完毕。也许你之前就已经启动过机器人？