题目描述

一条长走廊上排列着 $N$ 盏灯，灯的编号从 $1$ 到 $N$。每盏灯的状态为关闭或开启。存在一种特殊机制可改变灯的状态。在一次操作中，我们可以执行以下三种操作之一：

• 选择满足 $1 \le p \le q \le N$ 的整数 $p$ 和 $q$，并将灯 $p, p+1, \dots, q$ 全部关闭。
• 选择满足 $1 \le p \le q \le N$ 的整数 $p$ 和 $q$，并将灯 $p, p+1, \dots, q$ 全部开启。
• 选择满足 $1 \le p \le q \le N$ 的整数 $p$ 和 $q$，并将灯 $p, p+1, \dots, q$ 的状态全部翻转（关闭变开启，开启变关闭）。

灯的当前状态由长度为 $N$ 的字符串 $A$ 表示。若灯 $i$（$1 \le i \le N$）处于关闭状态，则字符串 $A$ 的第 $i$ 个字符为 $0$；若处于开启状态，则为 $1$。我们希望将灯的状态变为由长度为 $N$ 的字符串 $B$ 所表示的目标状态，且操作次数尽可能少。若希望灯 $i$（$1 \le i \le N$）处于关闭状态，则字符串 $B$ 的第 $i$ 个字符为 $0$；若希望其处于开启状态，则为 $1$。

请编写一个程序，输入灯的数量、当前状态和目标状态，计算并输出达到目标状态所需的最少操作次数。

输入格式

从标准输入读取以下数据：

$N$

$A$

$B$

输出格式

向标准输出写入一行。该行应包含达到目标状态所需的最少操作次数。

8
11011100
01101001

4

13
1010010010100
0000111001011

3

18
001100010010000110
110110001000100101

5

提示

数据范围

• $1 \le N \le 1000000$。
• $A$ 和 $B$ 均为长度为 $N$ 的字符串。
• 字符串 $A$ 和 $B$ 中的每个字符均为 $0$ 或 $1$。

子任务

1. （6 分）$N \le 18$。
2. （41 分）$N \le 2000$。
3. （4 分）字符串 $A$ 中的每个字符均为 $0$。
4. （49 分）无额外约束。

翻译由 Qwen3-235B 完成