Words

A word is a sequence of capital letters of the English alphabet. The length of a word is the number of letters it contains. For example, the word $\alpha$ = ABAACBBBA has length $9$.

A block of a word is a maximal run of identical letters. A word is $t$-hard if it consists of exactly $t$ blocks. The word $\alpha$ above is $6$-hard, because it splits into the blocks A | B | AA | C | BBB | A.

Two words of the same length can be compared by how much they differ. Two words of length $n$ are $k$-different if they differ in exactly $k$ positions $i$ (with $1 \le i \le n$): the $i$-th letter of the first word differs from the $i$-th letter of the second. For example, $\alpha$ and $\beta$ = AAAABBBBB are $3$-different.

Given a word $\alpha$, we want a word $\beta$ that is not too different from $\alpha$ yet as simple as possible, and we ask how simple $\beta$ can be.

Write a program that reads $n$, $k$, and a word $\alpha$ of length $n$, and finds the smallest $t$ such that there exists a $t$-hard word $\beta$ differing from $\alpha$ in at most $k$ positions. Output this value of $t$.

The first line contains two integers $n$ and $k$ separated by a single space ($1 \le n \le 1000$, $0 \le k \le n$): the length of the word $\alpha$ and the allowed number of differing positions. The second line contains exactly $n$ capital letters forming the word $\alpha$.

Output a single integer: the minimum value of $t$.