Edit Distance

Vantage Records reconciles two spellings of the same customer name — one keyed by a clerk, one pulled from a scanned form. Before a human is asked to look, the system scores how far apart the two spellings are: the number of single-character corrections needed to turn the first into the second. A correction is one of three things — type a character in, delete a character, or overwrite one character with another — and each counts as one.

Task: Print the smallest number of single-character corrections that turns the first spelling into the second.

Input

Two lines. The first holds the original spelling, the second holds the target spelling. Each is up to 500 lowercase letters. Either line may be empty.

Output

One line holding a single integer: the fewest corrections needed. Every insert, delete and overwrite counts as exactly 1, whatever the characters involved. Print 0 when the two spellings already match.

Example:

Input:
horse
ros

Output:
3