1300: E-解救艾希

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:4 Solved:0

Description

在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄进入中毒状态。

不巧的是,在一次战斗中,弗雷尔卓德的英雄艾希被提莫的飞箭命中导致中毒,为了解救艾希,泰达米尔决定偷袭提莫的营地获取解药。不巧的是,即使突袭非常顺利,提莫还是隐身逃跑了,但是装有解药的箱子被泰达米尔抢了过来。

这个箱子是一个特制的密码箱,需要正确回答箱子上的问题才能成功打开箱子拿到解药。

箱子的问题如下:

现在给定2个字符串ABAB都是由小写字母和问号组成的,问号可以变成任意字符(注意:‘ ? ’ 为英文字符!!!!!)

请你找出最短的字符串S,要求S包含AB两个字符串,只需要计算出所有符合要求的长度最短的S的长度L即可打开箱子。

这下泰达米尔傻眼了,于是只好求助你来解决这个问题,你能够解决这个问题成功解救艾希吗?

Input

第一行一个字符串A∣A∣≤6000。第二行一个字符串B, ∣B∣≤6000。(|A|代表字符串A的长度)

Output

输出最短字符串S的长度L

Sample Input Copy

abcd
?de

Sample Output Copy

5

HINT

样例解释:

最短的S为“abcde”,其中包含了“abcd”和“?de”,其中'?'变成‘c’



子串解释:

串中任意个连续的字符组成的子序列称为该串的子串

如“abc”是“abcde”的子串,但不是“adbc”的子串