단어

단어는 영어 대문자로 이루어진 수열이다. 단어의 길이는 그 안에 들어 있는 글자의 개수이다. 예를 들어 단어 $\alpha$ = ABAACBBBA의 길이는 $9$이다.

단어 안의 블록은 같은 글자가 이어지는 극대 구간이다. 어떤 단어가 정확히 $t$개의 블록으로 이루어져 있으면 그 단어를 $t$-hard라고 부른다. 위의 단어 $\alpha$는 A | B | AA | C | BBB | A의 $6$개 블록으로 나뉘므로 $6$-hard이다.

길이가 같은 두 단어는 서로 얼마나 다른지 비교할 수 있다. 길이가 $n$인 두 단어가 정확히 $k$개의 위치 $i$ ($1 \le i \le n$)에서, 즉 첫째 단어의 $i$번째 글자와 둘째 단어의 $i$번째 글자가 서로 다를 때, 두 단어를 $k$-different라고 한다. 예를 들어 $\alpha$와 $\beta$ = AAAABBBBB는 $3$-different이다.

주어진 단어 $\alpha$에 대해, $\alpha$와 너무 다르지 않으면서도 가능한 한 단순한 단어 $\beta$를 구하려 한다. $\beta$가 얼마나 단순해질 수 있는지가 문제이다.

$n$, $k$, 그리고 길이가 $n$인 단어 $\alpha$를 입력받아, $\alpha$와 많아야 $k$개의 위치에서만 다른 $t$-hard 단어 $\beta$가 존재하도록 하는 가장 작은 $t$를 구하는 프로그램을 작성하라. 그 $t$의 값을 출력한다.

첫째 줄에 두 정수 $n$과 $k$가 공백 하나로 구분되어 주어진다 ($1 \le n \le 1000$, $0 \le k \le n$). 각각 단어 $\alpha$의 길이와 허용되는 서로 다른 위치의 개수를 뜻한다. 둘째 줄에는 단어 $\alpha$를 이루는 정확히 $n$개의 대문자가 주어진다.

$t$의 최솟값을 나타내는 정수 하나를 출력한다.