Message

题意翻译

现在有A,B两个字符串，现在希望做尽可能少的操作，使得B成为A的子串（也可以是A本身）。操作有三种： 1、删掉某一个字符 2、加入一个字符 3、替换一个字符 求最少操作次数

题目描述

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.

输入输出样例

输入样例 #1

aaaaa
aaa

输出样例 #1

0

输入样例 #2

abcabc
bcd

输出样例 #2

1

输入样例 #3

abcdef
klmnopq

输出样例 #3

7

说明

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.