题目描述

给定两个长度相同的由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$。

---

示例输入1

1010
1100

示例输出1

3

以下是实现目标的一种最快方法：

• 翻转$A_1$：$A = 0010$
• 将$A$向左移动：$A = 0100$
• 再次翻转$A_1$：$A = 1100$

---

示例输入2

1
0

示例输出2

-1

无法翻转$A$中唯一的位。

---

示例输入3

11010
10001

示例输出3

4

以下是实现目标的一种最快方法：

• 将$A$向右移动：$A = 01101$
• 翻转$A_5$：$A = 01100$
• 将$A$向左移动：$A = 11000$
• 再次将$A$向左移动：$A = 10001$

---

示例输入4

0100100
1111111

示例输出4

5

按任意顺序翻转$A_1$、$A_3$、$A_4$、$A_6$和$A_7$。