Xâu nhị phân

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 (gồm các ký tự liên tiếp) 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.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên dương $n,k\le 2·{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).

Dữ liệu ra

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

Ràng buộc

• $1\le n,k\le 2·{10}^5$.
• Mỗi ký tự của $S$ là 0 hoặc 1.

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·{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 ngoài các ràng buộc đã nêu trong đề bài.

Ví dụ