{"code":"dhbbbitstr","name":"Xâu nhị phân (DHBB 2021)","description":"Cho xâu $S$ gồm $n$ ký tự $\\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\r\nchuỗ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\r\nthà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.\r\nYêu cầu: Cho biết số ký tự ít nhất trong xâu $S$ cần đảo.\r\n\r\n

Input

\r\n\r\nVào từ file văn bản BITSTR.INP\r\n- Dòng 1 chứa hai số nguyên dương $n, k \\le 2\\times 10^5$ cách nhau bởi dấu cách\r\n\r\n- Dòng 2 ghi xâu $S$ (gồm $n$ ký tự $\\in \\{0,1\\}$ viết liền nhau)\r\n\r\n

Output

\r\n\r\n- Ghi ra file văn bản BITSTR.OUT một số nguyên duy nhất là số ký tự ít nhất trong xâu $S$\r\ncần đảo.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($20\\%$ số điểm): $n \\le 20$\r\n- Subtask $2$ ($20\\%$ số điểm): $n, k \\le 400$\r\n- Subtask $3$ ($20\\%$ số điểm): $n \\le 2\\times 10^5\r\n; k \\le 400$\r\n- Subtask $4$ ($20\\%$ số điểm): $n \\le 2\\times 10^5\r\n; k \\le 5000$\r\n\r\n- 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.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 10 1\r\n 1000100011\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 4\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Biến đổi thành xâu gồm toàn ký tự 0\r\n 0000000000\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 6 2\r\n 010110\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 2\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Biến đổi thành:\r\n 000111 hoặc\r\n 111110 hoặc\r\n 011111","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}