Edit Distance

Problem statement

A spelling correction service transforms one word into another. Each insertion, deletion or replacement of a single character has the same cost, and the service must report the smallest number of edits needed. Your task Compute the Levenshtein edit distance from word1 to word2 using single-character insertion, deletion and replacement. Important details Matching characters need no edit. Swapping two characters is not a separate allowed operation. Either word may be empty, in which case all characters of the other must be inserted or deleted. Minimize total operations rather than choosing an arbitrary edit sequence. Worked example Transforming cat to cut needs one replacement of a with u. Therefore the distance is 1.

Input format

Two full lines: word1 then word2; either line may be empty.

Output format

Print the minimum edit count.

Constraints

0 <= lengths <= 500; lowercase English letters.

Sample input

cat
cut

Sample output

1