Problem Statement

You are given a string \(S\) of length \(n\) and a string \(T\) of length \(m\). Each character of the strings is one of 'a'–'z'.
Now, you want to convert \(S\) into \(T\) by successively applying any of the following 3 types of operations.
Among all such sequences of operations, consider one with the minimum number of operations, and write a program that outputs that minimum number.

(Operations)
[Change] Choose one character \(S\)[ i ] from \(S\) and change it to any character of your choice from 'a'–'z'.
[Delete] Choose one character \(S\)[ i ] from \(S\) and delete it. It is allowed for the string to become empty as a result of the deletion.
[Insert] Insert any one of the characters 'a'–'z' at any position of your choice in \(S\). In particular, you can also add a character at the beginning or the end of S.

Input

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

The first line contains integers \(n\), \(m\), representing the lengths of the strings \(S\), \(T\), separated by a space.
The following second and third lines contain the strings \(S\), \(T\), respectively.

\(1 \leq n, m \leq 1000\)
\(S\), \(T\) are strings consisting of 'a'–'z'

Output

Output the answer on 1 line.

Sample

9 9
abcdefghi
acdefxhij

3

3 4
abc
addc

2

14 16
pirikapirirara
poporinapeperuto

10