Edit Distance (Levenshtein Distance)


Find the edit distance between given two words s1 and s2.

The disntace is the minimum number of single-character edits required to change one word into the other. The edits including the following operations:

Input

s1
s2

Two words s1 and s2 are given in the first line and the second line respectively. The words will consist of lower case characters.

Output

Print the edit distance in a line.

Constraints

Sample Input 1

acac
acm

Sample Output 1

2

Sample Input 2

icpc
icpc

Sample Output 2

0