CF156A.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.

莫里亚蒂博士即将向夏洛克·福尔摩斯发送一条消息。他拥有一串字符串 $s$。

若字符串 $p$ 可以从字符串 $s$ 的某个位置开始连续读出，则称 $p$ 为 $s$ 的一个子串。例如，字符串 "aba" 共有六个子串："a"、"b"、"a"、"ab"、"ba"、"aba"。

莫里亚蒂博士计划从字符串 $s$ 中截取某个子串 $t$，然后对 $t$ 进行零次或多次变换，最终得到一个固定的目标字符串 $u$（即需发送给夏洛克·福尔摩斯的字符串）。一次变换定义为以下操作之一：

• 在字符串的任意一端插入一个字母；
• 从字符串的任意一端删除一个字母；
• 将字符串中的某一个字母替换为任意其他字母。

莫里亚蒂博士非常聪明；一旦选定子串 $t$，他总能以最少的变换次数将其变为 $u$。

请帮助莫里亚蒂博士从字符串 $s$ 的所有子串中选出最优的子串 $t$，使得将 $t$ 变换为 $u$ 所需的变换次数最少。

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.

第一行包含一个非空字符串 $s$，由小写拉丁字母组成。第二行包含一个非空字符串 $u$，由小写拉丁字母组成。两个字符串的长度均在 $1$ 到 $2000$（含）之间。

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

输出唯一的整数——即莫里亚蒂博士对你所选择的字符串所需进行的最少修改次数。

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.

在第一个样例中，莫里亚蒂可以任取一个长度为 3 的子串，该子串都将等于目标信息 u，因此莫里亚蒂无需进行任何修改。

在第二个样例中，应选取由第 2 到第 4 个字符组成的子串（即 "bca"），或由第 5 到第 6 个字符组成的子串（即 "bc"）。此时仅需进行一次修改：修改或添加最后一个字符。

在第三个样例中，初始字符串 s 不包含目标信息所需的任何字符，因此无论选择哪个子串，至少都需要进行 7 次修改才能得到目标信息。