Home

Contest: Task: Related: TaskE TaskG

Score : $600$ points

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.

Constraints

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

Input

Input is given from Standard Input in the following format:

$S$
$T$

Output

Print the answer.

Sample Input 1

0001
101

Sample Output 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

Sample Input 3

10101000010011011110
0010011111