题目描述

设 A 和 B 是 2 个字符串。要用最少的字符操作将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串 $A$ 变换为字符串 $B$ 所用的最少字符操作数称为字符串 $A$ 到 $B$ 的编辑距离，记为 $d(A,B)$。试设计一个有效算法，对任给的 $2$ 个字符串 $A$ 和 $B$，计算出它们的编辑距离 $d(A,B)$。

输入格式

第一行是字符串 $A$，文件的第二行是字符串 $B$。

输出格式

输出编辑距离 $d(A,B)$。

样例

输入#1

fxpimu 
xwrs

输出#1

5

数据范围

两个字符串长度均不超过 $2000$