B - Flip Digits 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

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 \leq N \leq 5 \times 10^5
  • S は 0,1 からなる長さ N の文字列．
  • T は 0,1 からなる長さ N の文字列．

入力

入力は以下の形式で標準入力から与えられる．

N
S
T

出力

S を T に一致させることが可能な場合，必要な最小の操作回数を出力せよ． 不可能な場合，-1 を出力せよ．

入力例 1

3
001
100

出力例 1

2

001 → (i=3 で操作) → 010 → (i=2 で操作) → 100 とすればよいです．

入力例 2

3
001
110

出力例 2

-1

入力例 3

5
10111
01010

出力例 3

5

Score : 600 points

Problem Statement

Given are length-N strings S and T consisting of 0 and 1. You can do the following operation on S any number of times:

  • Choose i (2 \leq i \leq N) such that S_i=1, and replace S_i with 0. Additionally, invert S_{i-1}, that is, change it to 1 if it is 0 now and vice versa.

Is it possible to make S exactly match T? If it is possible, how many operations does it take at least?

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • S is a string of length N consisting of 0 and 1.
  • T is a string of length N consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

N
S
T

Output

If it is possible to make S exactly match T, print the minimum number of operations it takes. Otherwise, print -1.

Sample Input 1

3
001
100

Sample Output 1

2

We can do as follows: 001 → (choose i=3) → 010 → (choose i=2) → 100.

Sample Input 2

3
001
110

Sample Output 2

-1

Sample Input 3

5
10111
01010

Sample Output 3

5