题目背景

Goose Tattarrattat 有一个仅由字符 0 和 1 组成的字符串。她希望通过若干次翻转操作，将这个字符串变成具有指定周期的形式。

题目描述

给定一个长度为 $N$ 的二进制字符串 $B$，以及一个正整数 $M$。

如果字符串 $B$ 的长度为 $N-M$ 的前缀与长度为 $N-M$ 的后缀完全相同，则称 $B$ 为一个 旋转序列。

等价地，对于所有满足

$$1 \le i \le N-M$$

的位置，都有

$$B_i=B_{i+M}.$$

也就是说，字符串中相距 $M$ 的两个对应位置必须相同。

你可以进行任意次操作。每次操作可以选择以下两种方式之一：

1. 选择字符串中的任意一个位置，将该位置的比特翻转：0 变为 1，1 变为 0；

2. 选择一个正整数 $k$，满足

   $$kM \le N,$$

   然后将字符串的前 $kM$ 个比特全部翻转。

请计算将初始字符串 $B$ 变成某个旋转序列所需的最少操作次数。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示二进制字符串的长度和目标周期。

第二行包含一个长度为 $N$ 的二进制字符串 $B$。

输出格式

输出一个整数，表示将 $B$ 变成某个旋转序列所需的最少操作次数。

数据范围

• $1 \le N \le 300$；
• $1 \le M \le N$；
• 字符串 $B$ 的长度恰好为 $N$；
• 字符串 $B$ 只包含字符 0 和 1。

样例 1

输入

8 1
00111000

输出

2

解释

先选择 $k=2$，翻转前 $2M=2$ 个比特，字符串变为 11111000。

再选择 $k=5$，翻转前 $5M=5$ 个比特，字符串变为 00000000。

最终字符串满足周期 $M=1$，共进行 $2$ 次操作。

样例 2

输入

12 3
101100001101

输出

2

样例 3

输入

8 4
11111111

输出

0

样例 4

输入

10 8
1101001000

输出

1

样例 5

输入

14 5
11011100101110

输出

4