题目描述

给定两个由 0 和 1 组成的长度为 $N$ 的字符串 $S$ 和 $T$。你可以对 $S$ 进行任意次以下操作：

• 选择一个满足 $S_i=$1 的 $i$（$2 \leq i \leq N$）。将 $S_i$ 替换为 0。同时，将 $S_{i-1}$ 改为与当前不同的字符。也就是说，如果操作前 $S_{i-1}$ 是 0，则改为 1；如果是 1，则改为 0。

你能否通过若干次操作使 $S$ 变为 $T$？如果可以，输出所需的最小操作次数；如果不可以，输出 $-1$。

输入格式

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

$N$ $S$ $T$

输出格式

如果可以将 $S$ 变为 $T$，输出所需的最小操作次数。如果不可以，输出 $-1$。

样例 1

输入

3
001
100

输出

2

样例 2

输入

3
001
110

输出

-1

样例 3

输入

5
10111
01010

输出

5

说明/提示

限制

• $1 \leq N \leq 5 \times 10^5$
• $S$ 是由 0 和 1 组成的长度为 $N$ 的字符串。
• $T$ 是由 0 和 1 组成的长度为 $N$ 的字符串。

样例解释 1

001 →（在 $i=3$ 处操作）→ 010 →（在 $i=2$ 处操作）→ 100，即可完成转换。

由 ChatGPT 4.1 翻译