题目描述

给定一个长度为 $N$ 的 $01$ 序列 $A$ 和一个正整数 $K$。你可以进行操作：选择序列中的一个元素 $A_i$，将其值修改（$0 \to 1$ 或 $1 \to 0$），每次操作的代价为 $1$。

你的目标是找到一个修改次数最少的方案，使得修改后的序列中不存在连续 $K$ 个相同元素。即，序列中不能出现连续 $K$ 个 $1$，也不能出现连续 $K$ 个 $0$。

请输出达到目标状态所需的最小总修改代价。

输入格式

第一行包含两个正整数 $N$ 和 $K$，分别表示序列长度和连续相同元素的上限。

第二行包含一个长度为 $N$ 的 $01$ 字符串，表示初始序列 $A$。

输出格式

输出一个整数，表示达到目标状态所需的最小修改代价。

5 3
11100

1

改为 01100

10 4
0000111100

2

一种可行解是 000(1)1(0)1100

12 3
111111111111

4

数据规模与约定

对于 $100\%$ 的数据，$1 \le N \le 2 \times 10^5$，$2 \le K \le 10$。

• 子任务 1（30 分）：保证 $N\le 20$。
• 子任务 2（30 分）：保证 $K=2$。
• 子任务 3（40 分）：没有特殊限制。