Зміна меж
У мегаполісі корів Бовінополісі відбувається перерозподіл районів! Це завжди викликає суперечки між двома основними породами корів, які там мешкають: голштинською та гернсейською. Обидві породи прагнуть зберегти свій вплив у місцевому уряді.
Бовінополіс складається з ланцюга з n пасовищ, на кожному з яких живе одна корова, що належить або до голштинської, або до гернсейської породи.
Уряд Бовінополіса планує розділити цю територію на кілька суміжних районів так, щоб у кожному районі було не більше k пасовищ, і кожне пасовище входило лише до одного району. Оскільки уряд контролюється голштинами, вони прагнуть організувати райони так, щоб мінімізувати кількість районів, де гернсейці мають більшість або де кількість корів обох порід однакова (такий район вважається рівним).
Коаліція гернсейців, стурбована цим процесом, намагається зрозуміти, якої шкоди може завдати цей перерозподіл. Допоможіть їм визначити найменшу можливу кількість районів, де гернсейці матимуть більшість або де райони будуть рівними.
Вхідні дані
Перша строка містить два цілих числа n (1 ≤ n ≤ 3 * 10^5) і k (1 ≤ k ≤ n). Друга строка містить рядок довжини n, де кожен символ - це 'H' або 'G', що позначає голштинську або гернсейську корову відповідно.
Вихідні дані
Виведіть мінімальну можливу кількість районів, де гернсейці матимуть більшість або де райони будуть рівними.