Копито, Папір, Ножиці (Золото)
Можливо, ви чули про гру "Камінь, Ножиці, Папір". Корови люблять грати в схожу гру "Копито, Ножиці, Папір". Правила гри "Копито, Ножиці, Папір" прості. Дві корови грають одна проти одної. Вони обидві рахують до трьох, а потім одночасно роблять жест, що представляє копито, ножиці або папір. Копито перемагає ножиці, ножиці перемагають папір, папір перемагає копито. Звісно, може бути нічия, якщо обидві корови зробили один і той самий жест.
Фермер Джон хоче зіграти з Бессі n разів. Бессі, будучи експертом у цій грі, може передбачити кожен з жестів ФД. Але як корова, вона дуже лінива. Тому вона хоче грати одним і тим самим жестом багато разів поспіль. Насправді, вона хоче переключатися між жестами не більше ніж k разів за всі ігри. Наприклад, якщо k = 2, вона може грати "копито" перші ігри, потім переключитися на папір і в кінці грати знову "копито".
За послідовністю жестів, яку зіграє ФД, визначте максимальну кількість ігор, які може виграти Бессі.
Вхідні дані
Перша рядок містить числа n (1 ≤ n ≤ 10^5) і k (0 ≤ k ≤ 20). Решта n рядків містять жести ФД, кожен H, P або S.
Вихідні дані
Виведіть максимальну кількість ігор, які може виграти Бессі, якщо вона може переключатися не більше ніж k разів.