说明

时间限制：1 Sec 内存限制：256 MB 输入文件：expr.in 输出文件：expr.out

给定由小写字母、?、* 构成的两段简化正则表达式字符串 $A,B$。

符号规则：

- ?：代表它前一个字符重复 $0$ 次或 $1$ 次；

- *：代表它前一个字符重复 $0$ 次及以上任意次。

设 $G_A$ 为正则 $A$ 能生成的全部字符串集合，$G_B$ 为正则 $B$ 能生成的全部字符串集合。

举例：$A=\texttt{a?b*}$ 时，$G_A=\{\texttt{""},\texttt{"a"},\texttt{"b"},\texttt{"ab"},\texttt{"bb"},\texttt{"abb"},\texttt{"bbb"},\texttt{"abbb"},\dots\}$。

对于仅由小写字母构成的字符串 $a,b$，定义编辑距离 $d(a,b)$：

将字符串 $a$ 变换为 $b$，仅允许单次插入、删除、替换一个字符，所需操作的最小次数。

举例：字符串 $\texttt{abcdefgh}$ 变为 $\texttt{zcdefgha}$，操作依次为删除首字符 a、将 b 替换为 z、末尾插入 a，共 $3$ 步，因此 $d(\texttt{abcdefgh},\texttt{zcdefgha})=3$。

定义正则表达式距离 $D(A,B) = \min\limits_{(a,b)\in G_A \times G_B} d(a,b)$。也就是从 $A$、$B$ 各自能生成的所有字符串配对中，取出编辑距离的最小值。

请你求出 $D(A,B)$。

输入格式

第一行字符串 $A$。

第二行字符串 $B$。

对于 100% 的数据，满足：

1、$A,B$ 仅由小写字母、?、* 组成；

2、? 和 * 不会连续出现，输入不含 ??、?*、*?、** 这类子串；

3、$A,B$ 的首字符一定是小写字母，不会是 ? 或 *。

输出格式

输出一行整数 $D(A,B)$。

样例

样例 1

ab?c
abc

0

样例说明：

$G_A=\{\texttt{ac},\texttt{abc}\}$，$G_B=\{\texttt{abc}\}$。

$d(\texttt{ac},\texttt{abc})=1$，$d(\texttt{abc},\texttt{abc})=0$，最小值为 $0$。

样例 2

a*bcd
aaaabd?

1

样例说明：

取 $a=\texttt{aaaabcd}$、$b=\texttt{aaaabd}$，二者编辑距离为 $1$，这是全局最小值。

样例 3

aaaaabbbaaaaa
a*b?c*

3

样例说明：

不选用 b? 带来的 b 字符，取 $b=\texttt{aaaaaaaaaaaaa}$，此时编辑距离为 $3$，为最小值。

样例 4

aaaaabbbaaaaa
a*b?a*

2

样例说明：

选用 b? 生成一个 b，取 $b=\texttt{aaaaaabaaaaaaa}$，此时编辑距离为 $2$，为最小值。

数据范围

对于 24% 的数据，$A,B$ 中没有 ? 和 *。

另外 12% 的数据，只有 ? 没有 *。

另外 20% 的数据，只有 * 没有 ?，$A,B$ 中有一个没有 ? 和 *。

另外 16% 的数据，$A,B$ 中只有一个有 ? 和 *。

另外 8% 的数据，$|A|,|B| \le 10$。

对于 100% 的数据，满足：$1 \le |A| \le 2000$，$1 \le |B| \le 2000$。