题目描述

设$\red A$和$\red B$是两个字符串。我们要用最少的字符操作次数，将字符串$\red A$转换为字符串$\red B$。这里所说的字符操作共有三种：

$\red 1$、删除一个字符；

$\red 2$、插入一个字符；

$\red 3$、将一个字符改为另一个字符；

！皆为小写字母！

输入格式

第一行为字符串$\red A$；第二行为字符串$\red B$；字符串$\red A$和$\red B$的长度均小于$\red{2000}$。

输出格式

只有一个正整数，为最少字符操作次数。

样例

输入样例

sfdqxbw
gfdgw

输出样例

4