B. Зухаир и строки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана строка $$$s$$$ длины $$$n$$$ и целое число $$$k$$$ ($$$1 \le k \le n$$$). Скажем, что строка $$$s$$$ имеет уровень $$$x$$$, если $$$x$$$ это наибольшее неотрицательное целое число, такое что в строке $$$s$$$ можно выбрать:

  • $$$x$$$ непересекающихся подстрок длины $$$k$$$,
  • все символы в этих $$$x$$$ подстроках должны быть одинаковы (т.е. каждая подстрока содержит только один различный символ, который один и тот же для всех выбранных подстрок).

Подстрока — это последовательность подряд идущих символов строки, подстрока определяется парой целых чисел $$$i$$$ и $$$j$$$ ($$$1 \le i \le j \le n$$$), обозначается как $$$s[i \dots j]$$$ = «$$$s_{i}s_{i+1} \dots s_{j}$$$».

Например, если $$$k = 2$$$, то:

  • строка «aabb» имеет уровень $$$1$$$ (можно выбрать подстроку «aa»),
  • строки «zzzz» и «zzbzz» имеют уровень $$$2$$$ (можно выбрать две непересекающихся подстроки «zz» в каждой их них),
  • строки «abed» и «aca» имеют уровень $$$0$$$ (невозможно выбрать хотя бы одну подстроку длины $$$k=2$$$, которая содержит один различный символ).

Зухаир дал вам целое число $$$k$$$ и строку $$$s$$$ длины $$$n$$$. Вам нужно найти $$$x$$$ — уровень строки $$$s$$$.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — длину строки и значение $$$k$$$.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.

Выходные данные

Выведите одно целое число $$$x$$$ — уровень строки.

Примеры
Входные данные
8 2
aaacaabb
Выходные данные
2
Входные данные
2 1
ab
Выходные данные
1
Входные данные
4 2
abab
Выходные данные
0
Примечание

В первом примере мы можем выбрать $$$2$$$ непересекающиеся строки, состоящей из буквы «a»: «(aa)ac(aa)bb», так что уровень равен $$$2$$$.

Во втором примере мы можем выбрать или подстроку «a» или «b» чтобы получить ответ $$$1$$$.