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

9 3
ABAACBBBA

2

Autor zadania: Tomasz Idziaszek.