Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Słowa (slo)

Słowa

Limit pamięci: 32 MB

Na potrzeby tego zadania słowem nazwiemy niepusty ciąg wielkich liter alfabetu angielskiego. Długością słowa jest liczba zawartych w nim liter. Tak więc ABAACBBBA jest przykładem słowa o długości 9. Blokiem w słowie nazywamy maksymalny, spójny podciąg takich samych liter. Powiemy, że słowo jest -trudne, jeśli zawiera bloków. Nasze przykładowe słowo jest 6-trudne, ponieważ składa się z bloków A|B|AA|C|BBB|A.

Jeśli dwa słowa mają taką samą długość, to możemy badać, jak bardzo się różnią. Dwa słowa o długości są -niepodobne, jeśli dla dokładnie indeksów (), -ta litera pierwszego słowa jest inna niż -ta litera drugiego słowa. Jeśli weźmiemy słowo AAAABBBBB, to słowa i są 3-niepodobne.

Dla danego słowa , chcemy znaleźć niezbyt różniące się od niego słowo , które nie będzie na dodatek zbyt trudne. Twoim zadaniem będzie stwierdzić na ile łatwe może być słowo .

Zadanie

Napisz program, który:

wczyta liczby i słowo o długości ;
wyznaczy minimalne , takie że istnieje słowo -trudne, które jest co najwyżej -niepodobne do wczytanego słowa (to znaczy, że nie istnieje takie, że słowa i są -niepodobne);
wypisze wynik.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oddzielone pojedynczym odstępem (, ). Oznaczają one odpowiednio: długość słowa i dopuszczalny stopień niepodobieństwa. W drugim wierszu znajduje się -literowe słowo złożone z wielkich liter alfabetu angielskiego.

Wyjście

W jedynym wierszu wyjścia należy wypisać szukaną liczbę .

Przykład

Dla danych wejściowych:

9 3
ABAACBBBA

poprawną odpowiedzią jest:

Autor zadania: Tomasz Idziaszek.