题目描述

给定两个字符串 $S$ 和 $T$，你需要用最少的操作次数将 $S$ 变换为 $T$。每次操作可以执行以下三种之一：

1. 删除 $S$ 中的一个字符；
2. 在 $S$ 中插入一个字符；
3. 将 $S$ 中的一个字符修改为另一个字符。

$S$ 和 $T$ 均只包含小写字母。

输入格式

第一行为字符串 $S$；第二行为字符串 $T$。

$S$ 和 $T$ 的长度均小于 $2000$。

输出格式

输出一个正整数，表示将 $S$ 变换为 $T$ 所需的最少操作次数。

样例

sfdqxbw
gfdgw

4

提示

对于 $100 \%$ 的数据，$1 \le |S|, |T| \le 2000$。