给定两个长度相同的二进制字符串 $$$a$$$ 和 $$$b$$$。您可以对字符串$$$a$$$执行以下两种操作:
- 分别交换索引 $$$i$$$ 和 $$$j$$$ 处的任意两位 ($$$1 \le i, j \le n$$$),此操作的成本为 $$$|i - j|$$$,即 $$$i$$$ 和 $$$j$$$ 之间的绝对差。
- 选择任意索引 $$$i$$$ ($$$1 \le i \le n$$$) 并翻转(将 $$$0$$$ 更改为 $$$1$$$ 或 $$$1$$$ 更改为 $$$0$$$)该索引处的位。此操作的成本为 $$$1$$$。
求使字符串 $$$a$$$ 等于 $$$b$$$ 的最小成本。不允许修改字符串$$$b$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 字符串 $$$a$$$ 和 $$$b$$$ 的长度。
第二行和第三行分别包含字符串 $$$a$$$ 和 $$$b$$$。
字符串 $$$a$$$ 和 $$$b$$$ 的长度均为 $$$n$$$,并且仅包含“0”和“1”。
输出
输出使字符串 $$$a$$$ 等于 $$$b$$$ 的最小成本。
示例
输入 #1
3 100 001
输出 #1
2
输入 #2
4 0101 0011
输出 #2
1
注意
在第一个示例中,最佳解决方案之一是翻转索引 $$$1$$$ 和索引 $$$3$$$,字符串 $$$a$$$ 按以下方式更改: "100" $$$\to$$$ "000" $$$\to$$$ "001"。成本为 $$$1 + 1 = 2$$$。
另一个最佳解决方案是交换位和索引$$$1$$$和$$$3$$$,字符串$$$a$$$更改然后“100”$$$\到$$$“001”,成本也是$$$|1 - 3| = 2$$$。
在第二个示例中,最佳解决方案是交换索引 $$$2$$$ 和 $$$3$$$ 处的位,字符串 $$$a$$$ 更改为“0101”$$$\to$$$“0011”。成本为 $$$|2 - 3| = 1$$$。