Đoạn nhị phân gần nhất

Cho hai xâu nhị phân $S,T$, $|T|\le |S|$. Có thể đổi một số ký tự của $T$; hãy tìm số đổi nhỏ nhất để $T$ trùng với một đoạn liên tiếp của $S$.

Input

• Hai dòng lần lượt chứa hai xâu nhị phân $S$ và $T$.

Output

• In số ký tự ít nhất phải đổi.

Constraints

• $1\le |T|\le |S|\le 10^6$; hai xâu chỉ gồm $0$ và $1$.

Scoring

• Subtask $1$ ($50$ điểm): Kích thước dữ liệu và số lượng token đủ nhỏ để có thể kiểm tra trực tiếp.
• Subtask $2$ ($50$ điểm): Không có ràng buộc bổ sung.

Example

001111
11

0