Home

Problem Statement

You have two strings $A = A_1 A_2 ... A_n$ and $B = B_1 B_2 ... B_n$ of the same length consisting of $0$ and $1$.

You can transform $A$ using the following operations in any order and as many times as you want:

• Shift $A$ by one character to the left (i.e., if $A = A_1 A_2 ... A_n$, replace $A$ with $A_2 A_3 ... A_n A_1$).
• Shift $A$ by one character to the right (i.e., if $A = A_1 A_2 ... A_n$, replace $A$ with $A_n A_1 A_2 ... A_{n-1}$).
• Choose any $i$ such that $B_i = 1$. Flip $A_i$ (i.e., set $A_i = 1 - A_i$).

You goal is to make strings $A$ and $B$ equal.

Print the smallest number of operations required to achieve this, or $-1$ if the goal is unreachable.

Constraints

• $1 \leq |A| = |B| \leq 2,000$
• $A$ and $B$ consist of $0$ and $1$.

Sample Input 1

1010
1100

Sample Output 1

3

Here is one fastest way to achieve the goal:

• Flip $A_1$: $A = 0010$
• Shift $A$ to the left: $A = 0100$
• Flip $A_1$ again: $A = 1100$

Sample Input 2

1
0

Sample Output 2

-1

There is no way to flip the only bit in $A$.

Sample Input 3

11010
10001

Sample Output 3

4

Here is one fastest way to achieve the goal:

• Shift $A$ to the right: $A = 01101$
• Flip $A_5$: $A = 01100$
• Shift $A$ to the left: $A = 11000$
• Shift $A$ to the left again: $A = 10001$

Sample Input 4

0100100
1111111

Sample Output 4

5

Flip $A_1$, $A_3$, $A_4$, $A_6$ and $A_7$ in any order.