题目描述

设 $A$ 和 $B$ 是 $2$ 个字符串。要用最少的字符操作将字符串 $A$ 转换为字符串 $B$ 。这里所说的字符操作包括：

(1) 删除 $A$ 一个字符；

(2) 在 $A$ 中插入一个字符；

(3) 将 $A$ 一个字符改为另一个字符。

将字符串 $A$ 变换为字符串 $B$ 所用的最少字符操作数称为字符串 $A$ 到 $B$ 的编辑距离，记为 $d(A,B)$ 。试设计一个有效算法，对任给的 $2$ 个字符串 $A$ 和 $B$ ，计算出它们的编辑距离 $d(A,B)$ 。

输入

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

字符串 $A$ 和 $B$ 都不含空格，字符串长度 ≤ 1800。

输出

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

样例

fxpimu
xwrs

5