配点: $500$ 点

問題文

いま、電光掲示板に 0 と 1 から成る長さ $N$ の文字列 $S$ が表示されています。

あなたは次の操作を何回でも行うことができます。なお、ここでは電光掲示板に表示されている文字列の $i$ $(1 \leq i \leq N)$ 文字目を $S_i$ と表します。

操作　整数 $(l, r)$ $(1 \leq l < r \leq N)$ であって、次の条件のうちいずれかを満たすものを $1$ 組選び、$S_l$ と $S_r$ を入れ替える。

• $S_l=$ 0 かつ $S_{l+1}=\cdots=S_r=$ 1 を満たす。
• $S_{l}=\cdots=S_{r-1}=$ 1 かつ $S_r=$ 0 を満たす。

電光掲示板に表示されている文字列を $T$ に一致させることができるか判定し、可能な場合は操作回数として考えられる最小の値を求めてください。

制約

• $2 \leq N \leq 500000$
• $S$ は 0 と 1 からなる長さ $N$ の文字列である
• $T$ は 0 と 1 からなる長さ $N$ の文字列である

入力

入力は以下の形式で標準入力から与えられます。

$N$

$S$

$T$

出力

電光掲示板に表示されている文字列を $T$ にすることが不可能な場合は、-1 を出力してください。

可能な場合は、操作回数として考えられる最小の値を出力してください。

7
1110110
1010111

2

例えば以下のように操作を行えば、$2$ 回の操作で電光掲示板に表示されている文字列を 1010111 にすることができます。

• $(l, r) = (2, 4)$ を選んで操作を行う。そのとき、電光掲示板の文字列は 1110110 から 1011110 に変化する。
• $(l, r) = (4, 7)$ を選んで操作を行う。そのとき、電光掲示板の文字列は 1011110 から 1010111 に変化する。

20
11111000000000011111
11111000000000011111

0

操作を行う前の時点で、電光掲示板に表示されている文字列が $T$ であるため、答えは $0$ となります。

6
111100
111000

-1

どのように操作を行っても、電光掲示板に文字列 $T$ を表示させることが不可能な場合は、-1 と出力してください。

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

22