Edit Distance

Consider an edit script that turns string $A$ into string $B$. An edit script is made of the four commands below, and each command consumes $A$ from the front while building the result string.

• Add (a): output one character to the result. $A$ is left untouched.
• Delete (d): remove the first character of $A$ and output nothing.
• Modify (m): remove the first character of $A$ and output a different character instead.
• Copy (c): remove the first character of $A$ and output that same character.

Copy is free. The length of an edit script is the number of add, delete, and modify commands it uses, and the shortest edit script is the one that minimizes the count of these three commands.

Given two strings $A$ and $B$, find the minimum number of add, delete, and modify commands (the edit distance) used by a shortest edit script that turns $A$ into $B$.

The first line contains string $A$ and the second line contains string $B$. Both strings consist only of English letters (uppercase and lowercase) and digits, and each has length between $1$ and $17000$, inclusive.

Print a single integer: the minimum number of add, delete, and modify commands needed to turn $A$ into $B$.