408504: GYM103158 I Binary string

Khaled Hamed challenged Compiler to solve this problem:

Given a binary string $$$S$$$ of length $$$N$$$ and an integer $$$K$$$. In one operation you can change one character that wasn't changed before. Find the minimum number of operations $$$X$$$ such that we can make every $$$S_i = S_{i+k}$$$ for all $$$(1 \leq i \leq N-K)$$$ in exactly $$$X$$$ operations.

Compiler laughed and solved the problem in one femtosecond ($$$10^{-15}$$$ second). Then Compiler challenged Khaled Hamed to solve this problem:

Given a binary string $$$S$$$ of length $$$N$$$ and an integer $$$X$$$. In one operation you can change one character that wasn't changed before. Find the minimum postive $$$K$$$ such that we can make every $$$S_i = S_{i+k}$$$ for all $$$(1 \leq i \leq N-K)$$$ in exactly $$$X$$$ operations.

It's guaranteed that each given test has a solution of less than $$$N$$$.

The first line of the input contains two integers $$$N$$$ and $$$X$$$ $$$(2 \leq X \leq N \leq 2000)$$$.

The second line contains binary string $$$S$$$.

Find the minimum K such that the condition is satisfied.

9 6
110010011

3

8 4
10110100

1