I. Binary string
time limit per test
2 seconds
memory limit per test
64 megabytes
input
binary.in
output
standard output

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$$$.

Input

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$$$.

Output

Find the minimum K such that the condition is satisfied.

Examples
Input
9 6
110010011
Output
3
Input
8 4
10110100
Output
1