問題文

文字列 S と T が与えられます。
あなたは、文字列 S に対して以下の 3 種類の操作を行うことができます。

操作1：S 中の文字を 1 つ選び、削除する。
操作2：S 中の文字を 1 つ選び、別の文字に変更する。
操作3：S 中の適当な位置に、文字を 1 つ挿入する。

最小何回の操作で、文字列 S を T に一致させることができますか。

制約

• S の文字数は 1 以上 2000 以下
• T の文字数は 1 以上 2000 以下
• S, T は英小文字からなる

入力例 1

tokyo
kyoto

出力例 1

4

以下のような 4 回の操作を行うことで、tokyo を kyoto にすることができます。

• 1 文字目を削除する：okyo になる。
• 1 文字目を削除する：kyo になる。
• 3 文字目の後に t を追加：kyot になる。
• 4 文字目の後に o を追加：kyoto になる。

入力例 2

competitive
programming

出力例 2

10

入力例 3

abcdef
bdf

出力例 3

3