A8419 | Message

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.

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.

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