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 types of operations:

1. Delete one character.
2. Insert one character.
3. Replace one character with another.

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

Input Format

The first line contains string $A$. The second line contains string $B$. Both have length at most $2000$.

Output Format

Output a single positive integer, which is the minimum number of character operations.

sfdqxbw
gfdgw

4

Hint

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

Translated by ChatGPT 5