01串

题号：NC214466
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

01串是只包含字符'0'或者'1'的字符串。

现在给定一个长度为n的01串 $s_{1}s_{2}...s_{i}...s_{n}(s_i$ 代表01串中第i个字符)

求最少需要修改多少个字符，使得修改后的01串中每个长度为k的子串中0和1的数量相同。

即修改后的01串需要满足：对任意长度为k的子串 $s_{i}...s_{i+k-1}(1 \leq i \leq n-k+1)$ 满足串中0的数量等于1的数量

如果不存在长度为n且每个长度为k的子串中0和1的数量相同的01串，输出-1

(一个字符串中任意个连续的字符组成的子序列称为该串的子串)

(每次修改你可以选择任意一位字符将其赋值为0或1)

输入描述:

输入共两行

第一行两个正整数。

第二行一个长度为n的字符串，保证只包含字符'0'或者'1'。

输出描述:

输出共一行一个整数代表答案

示例1

输入

复制

8 4
10100010

输出

复制

说明

只需要将第5位的0修改成1即可。

修改后的01串为10101010。

修改后的字符串中共有5个长度为4的子串:"1010","0101","1010","0101","1010"

每个子串中0和1的数量相等(都为2)。

示例2

输入

复制

8 3
10100010

输出

复制

-1

说明

k为奇数，不存在一个长度为k的01串满足这个01串中01数量相等。