Dr. Moriarty is about to send a message to Sherlock Holmes. He has a string $*s*$.

String $*p*$ is called a substring of string $*s*$ if you can read it starting from some position in the string $*s*$. For example, string "aba" has six substrings: "a", "b", "a", "ab", "ba", "aba".

Dr. Moriarty plans to take string $*s*$ and cut out some substring from it, let's call it $*t*$. Then he needs to change the substring $*t*$ zero or more times. As a result, he should obtain a fixed string $*u*$ (which is the string that should be sent to Sherlock Holmes). One change is defined as making one of the following actions:

• Insert one letter to any end of the string.
• Delete one letter from any end of the string.
• Change one letter into any other one.

Moriarty is very smart and after he chooses some substring $*t*$, he always makes the minimal number of changes to obtain $*u*$.

Help Moriarty choose the best substring $*t*$ from all substrings of the string $*s*$. The substring $*t*$ should minimize the number of changes Moriarty should make to obtain the string $*u*$ from it.

Input

The first line contains a non-empty string $*s*$, consisting of lowercase Latin letters. The second line contains a non-empty string $*u*$, consisting of lowercase Latin letters. The lengths of both strings are in the range from $1$ to $2000$, inclusive.

Output

Print the only integer — the minimum number of changes that Dr. Moriarty has to make with the string that you choose.

Note

In the first sample Moriarty can take any substring of length $3$, and it will be equal to the required message $*u*$, so Moriarty won't have to make any changes.

In the second sample you should take a substring consisting of characters from second to fourth ("bca") or from fifth to sixth ("bc"). Then you will only have to make one change: to change or to add the last character.

In the third sample the initial string $*s*$ doesn't contain any character that the message should contain, so, whatever string you choose, you will have to make at least $7$ changes to obtain the required message.