题目描述

$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$ と出力してください。

输入格式

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

$A$ $B$

输出格式

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

题目大意

给你两个01串A和B，你可以进行以下3种操作：

1. 将A左移一位（如"0011" -> "0110"）
2. 将A右移一位（如"0011" -> "1001"）
3. 选择一个满足$B_i=1$的位置i，令$A_i=1-A_i$

问要使A和B相等至少要进行几次操作。

1010
1100

3

1
0

-1

11010
10001

4

0100100
1111111

5

提示

制約

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

Sample Explanation 1

目標を達成する最短の操作列を一つ示します。 - $A_1$ を反転: $A\ =\ 0010$ - $A$ を左にシフト: $A\ =\ 0100$ - $A_1$ を再度反転: $A\ =\ 1100$

Sample Explanation 2

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

Sample Explanation 3

目標を達成する最短の操作列を一つ示します。 - $A$ を右にシフト: $A\ =\ 01101$ - $A_5$ を反転: $A\ =\ 01100$ - $A$ を左にシフト: $A\ =\ 11000$ - $A$ を再度左にシフト: $A\ =\ 10001$

Sample Explanation 4

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