Cho xâu ~S~ gồm ~n~ ký tự ~s_i \in \{0, 1\}~ và số tự nhiên ~k~. Hãy tìm cách đảo một số ít nhất các ký tự của chuỗi ~S~ (đảo ký tự 0 thành ký tự 1 hoặc ngược lại) 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 các ký tự 0 hoặc chỉ chứa các ký tự 1.

Yêu cầu: Cho biết số ký tự ít nhất trong xâu ~S~ cần đảo.

Input

• Dòng 1 chứa hai số nguyên dương ~n, k \le 2 \cdot 10^5~ cách nhau bởi dấu cách.
• Dòng 2 ghi xâu ~S~ (gồm ~n~ ký tự ~\in \{0, 1\}~ viết liền nhau).

Output

• Ghi ra một số nguyên duy nhất là số ký tự ít nhất trong xâu ~S~ cần đảo.

Sample Input 1

10 1
1000100011

Sample Output 1

4

Giải thích ví dụ 1: Biến đổi thành xâu gồm toàn ký tự 0.

Sample Input 2

6 2
010110

Sample Output 2

2

Giải thích ví dụ 2: Biến đổi thành: 000111 hoặc 111110 hoặc 011111

Subtasks

• 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 \cdot 10^5; k \le 400~.
• Subtask 4 (20% số điểm): ~n \le 2 \cdot 10^5; k \le 5000~.
• Subtask 5 (20% số điểm): Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề bài.