A. Сообщение
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Доктор Мориарти посылает сообщение Шерлоку Холмсу. В его распоряжении имеется строка s.

Строка p называется подстрокой строки s, если ее можно прочитать, начиная с некоторой позиции в строке s. Например, у строки «aba» есть шесть подстрок: «a», «b», «a», «ab», «ba», «aba».

Доктор Мориарти планирует вырезать из строки s некоторую подстроку, назовем ее t. Потом он должен ноль или более раз изменить вырезанную подстроку t. В результате должна получиться фиксированная строка u (именно ее нужно отправить Шерлоку Холмсу). За одно изменение считается одно из следующих действий:

  • Вставить одну букву с любого конца строки.
  • Удалить одну букву с любого конца строки.
  • Заменить одну любую букву на любую другую.

Мориарти очень умен, поэтому после выбора какой-то подстроки t он всегда делает минимальное количество изменений, чтобы получить u.

Помогите Мориарти выбрать среди всех подстрок строки s наилучшую подстроку t такую, что количество сделанных им изменений для получения из нее строки u будет минимально.

Входные данные

В первой строке дана непустая строка s, состоящая из строчных букв латинского алфавита. Во второй строке дана непустая строка u, состоящая из строчных букв латинского алфавита. Длины обоих строк находятся в пределах от 1 до 2000 включительно.

Выходные данные

Выведите единственное число — минимальное количество изменений, которые придется выполнить доктору Мориарти с подстрокой, которую Вы выберете.

Примеры
Входные данные
aaaaa
aaa
Выходные данные
0
Входные данные
abcabc
bcd
Выходные данные
1
Входные данные
abcdef
klmnopq
Выходные данные
7
Примечание

В первом примере Мориарти может взять любую подстроку длины 3, и она будет равна требуемому сообщению u, так что никаких изменений Мориарти делать не придется.

Во втором примере надо взять подстроку, состоящую из символов со второго по четвертый («bca») или с пятого по шестой («bc»). Тогда придется сделать всего одно изменение: заменить или добавить последний символ.

В третьем примере исходная строка s не содержит ни одного символа, который должен быть в сообщении, так что, какую подстроку не возьми, придется сделать как минимум 7 изменений, чтобы получить требуемое сообщение.