Cleaning Robot

题面翻译

给定一个由 $2\times n$ 个格子组成的走廊。有一些格子是脏的。你会从 $(1,1)$ 释放一个机器人。每次操作机器人会选定离它最近的一个脏格子，移动到那个格子上并清理该格子，重复此操作直至全部脏格子被清理。

然而机器人如果在选定下一个清理的脏格子时，有两个或更多脏格子离它最近，那么机器人会崩溃。

你的任务是事先清理手动尽量少的脏格子，使得机器人可以正常清理完所有格子。

输出你清理完后剩下的脏格子数量。

题目描述

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.

输入格式

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.

输出格式

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

样例 #1

样例输入 #1

2
01
11

样例输出 #1

2

样例 #2

样例输入 #2

2
01
01

样例输出 #2

2

样例 #3

样例输入 #3

4
0101
1011

样例输出 #3

4

样例 #4

样例输入 #4

4
0000
0000

样例输出 #4

0

样例 #5

样例输入 #5

5
00011
10101

样例输出 #5

4

样例 #6

样例输入 #6

6
011111
111111

样例输出 #6

8

样例 #7

样例输入 #7

10
0101001010
1010100110

样例输出 #7

6

提示

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?