题目描述

给定长度为$N$的字符串$s$和$t$，其中$s$和$t$都由0和1组成，并且在这些字符串中，同一个字符不会连续出现三次或更多次。

你可以通过反复执行以下操作来修改$s$：

• 自由选择一个索引$i$($1 \\leq i \\leq N$)，并将$s$的第$i$个字符取反（即将0替换为1，将1替换为0），前提是操作后$s$中不会出现同一个字符连续出现三次或更多次。

你的目标是使得$s$等于$t$。找到所需最小操作数。

约束条件

• $1 \\leq N \\leq 5000$
• 字符串$s$和$t$的长度都为$N$。
• 字符串$s$和$t$只由0和1组成。
• 在字符串$s$和$t$中，同一个字符不会连续出现三次或更多次。

输入

从标准输入读入数据，输入格式如下：

$N$

$s$

$t$

输出

找到将$s$变为$t$所需的最少操作数。可以证明该目标在有限次操作内总是可以实现的。

样例输入 1

4
0011
0101

样例输出 1

4

一种可能的解法是：0011 → 1011 → 1001 → 1101 → 0101。

样例输入 2

1
0
0

样例输出 2

0

样例输入 3

8
00110011
10101010

样例输出 3

10