cho.sh

Minimum String Difference

Slide the shorter string A across every possible alignment position over B and output the minimum number of mismatched characters.

Easy3StringSliding windowBrute forceInterviewNo attempts yetTime limit2sMemory limit128 MB

Problem

For two strings X and Y of the same length, their difference is the number of positions i where X[i] and Y[i] are different.

You are given two strings A and B. The length of A is less than or equal to the length of B. You may repeatedly add any lowercase letter to the front or the back of A until the two strings have the same length.

Because added letters can be chosen freely, this is equivalent to aligning A with one contiguous substring of B that has the same length as A. Find the minimum possible difference after choosing the best alignment.

Input

The first line contains A and B.

Both strings consist only of lowercase English letters. Each string has length at most 50, and |A| <= |B|.

Output

Print the minimum possible difference between A and B after making their lengths equal.