Vũ Đạo Bò

Đội nhảy gồm $N$ con bò ($2\le N\le {10}^6$) đứng thành một hàng. Có hai loại bò: Guernsey (ký hiệu 0) và Holstein (ký hiệu 1). Mỗi bước nhảy, hai con bò cách nhau tối đa $K$ vị trí có thể hoán đổi chỗ.

Cho chuỗi nhị phân đầu tiên và cuối cùng của buổi nhảy (có cùng số ký tự '1'), tìm số bước nhảy tối thiểu để biến đổi chuỗi đầu thành chuỗi cuối.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $K$ ($1\le K\le N$)
• Dòng 2: Chuỗi nhị phân đầu tiên (độ dài $N$)
• Dòng 3: Chuỗi nhị phân cuối cùng (độ dài $N$)

Dữ liệu ra

Một số nguyên -- số bước nhảy tối thiểu.

Ràng buộc

• $2\le N\le {10}^6$
• $1\le K\le N$
• Hai chuỗi có cùng số ký tự '1'
• Test 4-5: $K=1$
• Test 6-7: Tối đa 8 ký tự '1'
• Test 8-15: $N\le 5000$

Ví dụ