問題文

長さが M の文字列 S と、長さが N の文字列 T が与えられます。

S に以下の 3 通りの操作を繰り返し施すことで、T に変換したいとします。そのような一連の操作のうち、操作回数の最小値を求めてください。なお。この最小値のことを文字列 S, T の編集距離と呼びます。

• 変更：文字列 S 中の文字を 1 つ選んで任意の文字に変更する
• 削除：文字列 S 中の文字を 1 つ選んで削除する
• 挿入：文字列 S の好きな箇所に好きな文字を 1 文字挿入する

入力例

5 6
abcde
bcdefg

出力例

3

文字列 S から先頭 1 文字 "a" を削除して、末尾に 2 文字 "fg" を付け加えることで T に一致します。よって、求める編集距離は 1 + 2 = 3 です。