Возможно Вы слышали об игре "Камень, Бумага, Ножницы". Коровы любят играть в похожую игру "Копыто, Бумага, Ножницы" Правила игры "Копыто, Бумага, Ножницы" просты. Две коровы играют друг против друга. Они обе считают до трёх, а затем одновременно делают жест, представляющий копыто, бумагу или ножницы. Копыто выигрывает у ножниц, ножницы выигрывают у бумаги, бумага выигрывает у копыта. Конечно может быть и ничья, если обе коровы сделали один и тот же жест.
Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним
и тем же жестом много раз подряд. В действительности, она хочет переключаться между жестами не более
чем \(K\) (\(0 \leq K \leq 20\)) раз за все игры.
Например, если \(K=2\), она может играть "копыто" первые игры, затем переключиться на
бумагу и в конце играть снова "копыто".
По последовательности жестов, которую сыграет ФД, определите максимальное количество
игр, которые может выиграть Бесси.
ФОРМАТ ВВОДА (файл hps.in):
Первая строка ввода содержит числа
\(N\) м
\(K\).
Оставшиеся \(N\) строк содержат жесты ФД, каждый H, P или S.
ФОРМАТ ВЫВОДА (файл hps.out):
Выведите максимальное количество игр, которые может выиграть Бесси,
если она может переключаться не более чем \(K\) раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1
P
P
H
P
S
|
4
|