AT_agc019_d [AGC019D] Shift and Flip

[problemUrl]: https://atcoder.jp/contests/agc019/tasks/agc019_d $ 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 $ と出力せよ。

### 制約 - $ 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 $ を任意の順序で反転すればよいです。