题目描述

给定由 0 和 1 组成的字符串 $S$ 和 $T$。
我们将改变 $T$ 中的一些字符，使得 $T$ 成为 $S$ 的子串。
至少需要改变多少个字符？

什么是子串？当 $S$ 的某个连续部分与 $T$ 匹配时，我们称 $T$ 是 $S$ 的子串。例如，000 是 10001 的子串，而 11 不是。

约束条件

• $S$ 和 $T$ 均由 0 和 1 组成。
• $1 ≤ |T| ≤ |S| ≤ 10^6$

输入

从标准输入中按以下格式给出输入：

$S$ $T$

输出

打印答案。

示例输入 1

0001
101

示例输出 1

1

将 $T$ 改为 001 可以使其与 $S$ 的第 $2$ 至第 $4$ 个字符匹配。

示例输入 2

0101010
1010101

示例输出 2

7

示例输入 3

10101000010011011110
0010011111

示例输出 3

1