The edit distance of two strings a and b is the minimum number of edit operations which transforms string a to b. The allowed operations are:

• Insert one character
• Delete one character
• Substitute one character

For example the edit distance of strings KITTEN and SITTING is 3:

1. KITTEN \rightarrow SITTEN (substitution of "S" for "K")
2. SITTEN \rightarrow SITTIN (substitution of "I" for "E")
3. SITTIN \rightarrow SITTING (insertion of "G" at the end)

Your task is to compute the minimum number of edit operations required.

Input

The first line of input contains string a with n characters between A-Z.

The second line of input contains string b with m characters between A-Z.

Output

Output the minimum number of edit operations required.

Limits

• 1 \le n,m \le 5000

Example

Input:

KITTEN
SITTING

Output:

3