配点 : $1000$ 点

問題文

$0$ と $1$ からなる同じ長さの二つの文字列 $A = A_1 A_2 ... A_n$ と $B = B_1 B_2 ... B_n$ があります。

あなたは、以下の操作を任意の順序で何度でも行って $A$ を変化させることができます。

• $A$ を一文字左にシフトする（すなわち、$A = A_1 A_2 ... A_n$ として $A$ を $A_2 A_3 ... A_n A_1$ に置き換える）。
• $A$ を一文字右にシフトする（すなわち、$A = A_1 A_2 ... A_n$ として $A$ を $A_n A_1 A_2 ... A_{n-1}$ に置き換える）。
• $B_i = 1$ であるような $i$ をいずれか一つ選び、$A_i$ を反転する（すなわち、$A_i = 1 - A_i$ とする）。

あなたの目標は文字列 $A, B$ を一致させることです。

これに必要な最小の操作回数を出力してください。ただし、これが不可能である場合は $-1$ と出力してください。

制約

• $1 \leq |A| = |B| \leq 2,000$
• $A, B$ は $0$ と $1$ からなる。

入力

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

$A$

$B$

出力

文字列 $A, B$ を一致させるために必要な最小の操作回数を出力せよ。ただし、これが不可能である場合は $-1$ と出力せよ。

1010
1100

3

目標を達成する最短の操作列を一つ示します。

• $A_1$ を反転: $A = 0010$
• $A$ を左にシフト: $A = 0100$
• $A_1$ を再度反転: $A = 1100$

1
0

-1

$A$ の唯一のビットを反転させる方法はありません。

11010
10001

4

目標を達成する最短の操作列を一つ示します。

• $A$ を右にシフト: $A = 01101$
• $A_5$ を反転: $A = 01100$
• $A$ を左にシフト: $A = 11000$
• $A$ を再度左にシフト: $A = 10001$

0100100
1111111

5

$A_1$, $A_3$, $A_4$, $A_6$, $A_7$ を任意の順序で反転すればよいです。