题目描述

小明是一个被派遣到美国的间谍，这一天神盾局开始调查起了小明的身份，于是布置给小明一道题目来检测他是否是间谍。由于这是一道性命攸关的大事，所以小明找来了机智的你，希望你能帮他逃脱险境。

神盾局给定小明一个字符串，小明可以对这个字符串进行插入一个字符，删除一个字符，替换一个字符。进而转换成小明心中的字符串，小明需要讲最少进行的插入\删除\替换的操作数告诉神盾局才能证明他不是间谍。

输入说明

第一行输入一行字符串表示神盾局给小明的字符串$s1$.

第二行输入一行字符串表示小明心中的字符串$s2$ .

输出说明

输出小明最少需要操作的次数

Example

输入：

abcd
dd

输出：

3

数据规模

对于$50\%$ 的数据 $s1, s2$的长度均小于等于$20$;

对于$100\%$的数据， $s1, s2$ 的长度均小于等于$1000$;