Các bạn bò đã thành lập 1 đội nhảy mới!!! Bác nông dân John được may mắn trở thành biên đạo của đội nhảy thế kỉ này. Điệu nhảy tuyệt vời nhất của đội bao gồm \(N\) bạn bò đứng thành 1 hàng \((1 \leq N \leq 10^6)\). Ở mỗi bước nhảy, 2 bạn bò cách nhau \(K\) vị trí \((1 \leq K < N)\) nhẹ nhàng nhảy lên và đáp xuống ở vị trí của bạn còn lại.

Mỗi bạn bò lại thuộc \(1\) trong \(2\) gia tộc bò khác nhau - nhà Guernseys và nhà Holsteins. Biên đạo John đã ghi chép lại điệu nhảy bằng \(1\) dãy các chuỗi nhị phân độ dài \(N\) với \(0\) là biểu diễn cho bạn bò nhà Guernseys, \(1\) là biểu diễn cho bạn bò nhà Holsteins, và các chuỗi nhị phân cho biết các bạn bò sẽ được sắp xếp như thế nào trong suốt điệu nhảy.

Nhưng không may thay, tên nông dân Nhoj xấu xa (biên đạo của đội nhảy đối thủ) đã đột nhập vào và xoá đi tất cả chuỗi nhị phân của John trừ chuỗi đầu tiên và cuối cùng! Một cuộc thi lớn đang sắp sửa diễn ra, bác đạo John không được phép tốn thêm thời gian để xây dựng lại các chuỗi nhị phân nữa.

Vì vậy, bác John đưa cho bạn \(2\) chuỗi nhị phân này, bạn hãy giúp bác tìm ra số bước nhảy ít nhất có thể để các bạn bò bắt đầu sắp xếp theo chuỗi nhị phân đầu tiên khi điều nhảy bắt đầu và theo chuỗi nhị phân cuối khi điệu nhảy kết thúc nhé!

Input

• Dòng đầu tiên gồm \(2\) số \(N\) và \(K\).
• Dòng thứ hai gồm chuỗi nhị phân đầu tiên.
• Dòng thứ ba gồm chuỗi nhị phân cuối cùng.

Output

• Số bước nhảy ít nhất có thể đạt được.

Scoring

• Subtask \(1\): \(K = 1\).
• Subtask \(2\): Có ít nhất \(8\) bạn bò đền từ nhà Vastaya.
• Subtask \(3\): \(N \leq 5000\).
• Subtask \(4\): Không có ràng buộc gì thêm.

Example

4 1
0111
1110

3

5 4
11000
00011

2