题目描述

设 $A$ 和 $B$ 是两个字符串。要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

对任意两个字符串 $A$ 和 $B$，计算出将 $A$ 变换为 $B$ 所用的最少操作次数。

输入格式

第一行：字符串 $A$。
第二行：字符串 $B$。

输出格式

一行，一个正整数，表示最少操作次数。

样例

sfdqxbw
gfdgw

4

样例解释
$A = \text{sfdqxbw}$，$B = \text{gfdgw}$。
一种最优方案为：

1. 将 's' 改为 'g'，$A$ 变为 gfdqxbw；
2. 将 'q' 改为 'g'，$A$ 变为 gfdgxbw；
3. 删除 'x'，$A$ 变为 gfdgbw；
4. 删除 'b'，$A$ 变为 gfdgw。
   共 $4$ 步。

数据范围

• 字符串 $A$ 和 $B$ 的长度均小于 $2000$。