Edit Distance

You are given two strings $a$ and $b$. In 1 operation you can do one of the following:

• Remove a character from $a$
• Insert a character into $a$
• Replace a character in $a$ with another character.

What is the number of operations to turn the string $a$ into $b$.

Input

The first line will contain the string $a$. The second line will contain the string $b$.

Output

Output the minimum number of operations to turn the string $a$ into $b$.

Constraints

• $1 \le | a |, | b | \le 10^3$

Example 1

bbababbbab
ababbabbbb

3

Example 2

eadbeadcbc
bebbbceeca

8

Example 3

ebdccedbcbbdddcedeab
abdcbcaaeababddedbcd

12