The Young Great Wizard of UTA

Once upon a time, two orphan boys fought to become the king of two countries. These two orphans were best friends, but their kingdom was always fighting with each other. They were distraught by the fact. So they met with the great land wizard to find a solution. The great wizard told them that every country in this world is based on a unique magical word, and their nations are always in a fight because the word is not similar. So if they want to stop these fights, they must change that magical word and make it comparable. Upon changing the base magical word, these two kingdoms will merge into one and form the new kingdom UTA. Now to change a single character in those words, they have to sacrifice one of their body parts, for example, a finger, a hand, a leg, etc. Each of these sacrifices will be counted as cost one. Also, there are only specific ways to change the characters in these magical words. One can not change it however they prefer to. The great wizard particularly informed the orphan kings about three ways to change the characters in a magical word —

• Insert a new character if the two base magical words are not similar in length, and one of them needs a new character to become identical to the other one.

• Delete an existing character if the two base magical words are not similar in length, and one of them must remove the character to become identical to the other one.

• Substitute a character if the two base magical words are not similar, and one of them must be substituted to become identical to the other one.

Each of these operations will take a year and one cost unit per operation.

Now they are in a dilemma about what to do. So they are now searching for a new young great wizard who can tell them what will be the minimum cost to create the new magical word which will be the new base of the kingdom of UTA.

Input

The first line of the input contains a string $s (1\le|s|\le1000)$ consisting of lowercase Latin letters, the first magical word.

The second line of the input contains a string $t (1\le|t|\le1000)$ consisting of lowercase Latin letters, the second magical word.

Output

In the single line of output print the minimum cost to build the new magical word.

Samples

Input	Output
Gilly Geelly	2

Input	Output
a a	0