Edit Distance

Problem Description

Let $A$ and $B$ be two strings. We want to transform string $A$ into string $B$ using the minimum number of character operations. There are three kinds of character operations:

1. delete a character;
2. insert a character;
3. change one character into another.

Both $A$ and $B$ contain only lowercase letters.

Input Format

The first line is the string $A$; the second line is the string $B$. Both strings have length less than $2000$.

Output Format

A single positive integer: the minimum number of character operations.

Sample Input

sfdqxbw
gfdgw

Sample Output

4

Hint

For 100% of the test data, $1 \le |A|, |B| \le 2000$.