Problem Statement

Given are strings S and T consisting of 0 and 1.
We will change some of the characters in T so that T becomes a substring of S.
How many characters do we need to change at least?

What is a substring?
T is said to be a substring of S when some contiguous part of S matches T.
For example, 000 is a substring of 10001, while 11 is not.

Input

Input is given from Standard Input in the following format:
S
T

Output

Print the answer.

Constraints

• Each of S and T consists of 0 and 1.
• 1 ≤ |T| ≤ |S| ≤ 10^6

Sample Input 1

0001
101

Sample Output 1

1

Changing T to 001 makes it match the 2-nd through 4-th characters of S.

Sample Input 2

0101010
1010101

Sample Output 2

7

Sample Input 3

10101000010011011110
0010011111

Sample Output 3

1

见题面 Input 部分

见题面 Output 部分