Cho xâu \(S\) gồm \(n\) ký tự thuộc \({0, 1}\) và một số tự nhiên \(k\).

Hãy tìm cách đảo ít nhất một số ký tự trong chuỗi \(S\)
(đảo ký tự \(0\) thành \(1\) hoặc \(1\) thành \(0\)) sao cho chuỗi kết quả có thể được phân tách thành không quá \(k\) chuỗi con, mà mỗi chuỗi con chỉ chứa toàn \(0\) hoặc toàn \(1\).

Yêu cầu

• Cho biết số ký tự ít nhất trong chuỗi \(S\) cần đảo để thỏa mãn điều kiện trên.

Dữ liệu vào

• Dòng 1: Hai số nguyên \(n\), \(k\) \((1 \le n, k \le 2·10^5)\)
• Dòng 2: Chuỗi nhị phân \(S\) gồm đúng \(n\) ký tự \(0\) hoặc \(1\).

Dữ liệu ra

• Một số nguyên duy nhất - là số ký tự tối thiểu cần đảo.

Ràng buộc

• Subtask 1 (20% số điểm): \(n \le 20\)
• Subtask 2 (20% số điểm): \(n, k \le 400\)
• Subtask 3 (20% số điểm): \(n \le 2·10^5\), \(k \le 400\)
• Subtask 4 (20% số điểm): \(n \le 2·10^5\), \(k \le 5000\)
• Subtask 5 (20% số điểm): Không có ràng buộc bổ sung.

Input 1

10 1
1000100011

Output 1

4

Input 2

6 2
010110

Output 2

2