問題文

長さ\(n\)の文字列\(S\)と長さ\(m\)の文字列\(T\)が与えられます。文字列を構成する各文字は、'a'～'z'です。
今、\(S\)に以下の3種類の操作のいずれかを順次実施して\(T\)に変換したいです。
そのような一連の操作のうち、操作回数の最小となるものについて、その最小値を出力するプログラムを書いて下さい。

(操作)
【変更】 \(S\)の中から文字\(S\)[ i ]を1個選んで、その文字を'a'～'z'のいずれかの好きな文字に変更します。
【削除】 \(S\)の中から文字\(S\)[ i ]を1個選んで、その文字を削除します。削除によって空文字列になることも許容します。
【挿入】 \(S\)の好きな箇所に、'a'～'z'のいずれかの文字を挿入します。特に、Sの先頭や最後尾に文字を追加することもできます。

入力

\(n\) \(m\)
\(S\)
\(T\)

一行目に文字列\(S\), \(T\)の長さを表す整数\(n\), \(m\)で空白区切りで与えられます。
続く二行目、三行目には、文字列\(S\), \(T\)がそれぞれ与えられます。

\(1 \leq n, m \leq 1000\)
\(S\), \(T\)は、'a'～'z'から構成される文字列です

出力

答えを1行に出力してください。

サンプル

9 9
abcdefghi
acdefxhij

3

3 4
abc
addc

2

14 16
pirikapirirara
poporinapeperuto

10