Cho xâu ~𝑆~ gồm ~𝑛~ ký tự ~∈ {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 ~𝑆~ (đả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á ~𝑘~ 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 ~𝑆~ cần đảo.

Dữ liệu:

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

Kết quả: Gồm một số nguyên duy nhất là số ký tự ít nhất trong xâu ~𝑆~ cần đảo.

Ví dụ

INPUT 1

10 1
1000100011

OUTPUT 1

4

INPUT 2

6 2
010110

OUTPUT 2

2

Giải thích

• Ở test 1, ta biến đổi thành xâu gồm toàn ký tự 0 0000000000
• Ở test 2, ta có thể biến đổi thành 000111 hoặc 111110 hoặc 011111

Bộ test chia làm 5 subtasks:

• Subtask 1 (20% số điểm): ~𝑛 ≤ 20~
• Subtask 2 (20% số điểm): ~𝑛, 𝑘 ≤ 400~
• Subtask 3 (20% số điểm): ~𝑛 ≤ 2*10^5; 𝑘 ≤ 400~
• Subtask 4 (20% số điểm): ~𝑛 ≤ 2*10^5; 𝑘 ≤ 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.