让我们表示函数$$$f(s)$$$,它接受由小写拉丁字母和点组成的字符串$$$s$$$,并返回由小写拉丁字母组成的字符串,如下所示:
1. 设 $$$r$$$ 为空字符串;
2.从左到右处理$$$s$$$的字符。对于每个字符 $$$c$$$,执行以下操作:如果 $$$c$$$ 是小写拉丁字母,则在字符串 $$$r$$$ 末尾附加 $$$c$$$;否则,从 $$$r$$$ 中删除最后一个字符(如果在删除最后一个字符之前 $$$r$$$ 为空 — 函数崩溃);
3. 返回 $$$r$$$ 作为函数的结果。
给定两个字符串 $$$s$$$ 和 $$$t$$$。您必须从 $$$s$$$ 中删除尽可能少的字符,以便 $$$f(s) = t$$$ (并且该函数不会崩溃)。请注意,您不允许将新字符插入 $$$s$$$ 或对现有字符重新排序。
输入
输入由两行组成:第一行包含 $$$s$$$ — 由小写拉丁字母和点组成的字符串,第二行包含 $$$t$$$ — 由小写拉丁字母组成的字符串 ($$$1 \le |t| \le |s| \le 10000$$$)。
对输入的附加约束:可以从 $$$s$$$ 中删除一些字符,以便 $$$f(s) = t$$$。
输出
打印一个整数 — 您必须从 $$$s$$$ 中删除的最小字符数,这样 $$$f(s)$$$ 不会崩溃并返回 $$$t$$$ 作为函数的结果。
示例
输入 #1
a.ba.b. abb
输出 #1
2
输入 #2
.bbac..a.c.cd bacd
输出 #2
3
输入 #3
c..code..c...o.d.de code
输出 #3
3