編集距離

２つの文字列 s1、s2 の編集距離（レーベンシュタイン距離）を求めて下さい。

編集距離とは、以下３種類の操作によって、１つの文字列を別の文字列に変形するのに必要な手順の最小回数です：

• 挿入: 文字列に１つの文字を挿入する。
• 削除: 文字列から１つの文字を削除する。
• 置換: 文字列の中の１文字を別な文字に置き換える。

入力

s1
s2

２つの文字列 s1, s2 がそれぞれ１行目と２行目に与えられる。文字列はアルファベットの小文字で構成されている。

出力

編集距離を１行に出力する。

制約

• 1 ≤ s1 の長さ ≤ 1000
• 1 ≤ s2 の長さ ≤ 1000

入力例 1

acac
acm

出力例 1

2

入力例 2

icpc
icpc

出力例 2

0

---