题目描述

两个字符串之间的编辑距离是将一个字符串转换成另一个字符串所需的最小操作次数。

允许的操作有：

• 向字符串中添加一个字符
• 从字符串中删除一个字符
• 替换字符串中的一个字符

例如，字符串 LOVE 和 MOVIE 之间的编辑距离是 $2$，因为你可以先将 L 替换为 M，然后再添加字符 I。

你的任务是计算两个字符串之间的编辑距离。

输入格式

第一行是一个包含 $n$ 个字符的字符串，其中字符是大写字母 $A \sim Z$。

第二行是一个包含 $m$ 个字符的字符串，其中字符是大写字母 $A \sim Z$。

输出格式

输出一个整数，表示两个字符串之间的编辑距离。

样例

LOVE
MOVIE

2

数据范围

• $1 \le n, m \le 5000$