题目描述

对于两个只含小写英文字母的字符串，可以进行删除一个字符、插入一个字符或把一个字符替换为另一个字符三种操作。请计算把字符串 $A$ 变成字符串 $B$ 至少需要多少次操作。

输入格式

第一行输入字符串 $A$，第二行输入字符串 $B$。

输出格式

输出一个整数，表示最少操作次数。

数据范围与约定

两个字符串的长度均小于 $2000$，且只含小写英文字母。

可见测试数据

输入数据 1

sfdqxbw
gfdgw

输出数据 1

4

输入数据 2

rcpw
wbl

输出数据 2

4

输入数据 3

hewwoadn
adwweodeq

输出数据 3

6