Решить задачу при помощи кода

В столовой одного известного Завода вот-вот начнётся обед. На обеде есть три гарнира — макарошки, пюрешка и греча. К гарнирам, конечно же, полагается горячее. Горячих блюд тоже три (ну и совпадение!) — сосиски, котлетки и кура. На раздаче сегодня стоит добрая повариха Алевтина Мстиславовна. Она немного ленива, но очень любит заводчан, вот перед ней и встала задача.

Итак, для начала поведаем вам прописные истины: макарошки лучше сочетать с сосисками, пюрешку с котлетками, а гречу с курой. Человек, у которого на обед одно из этих трёх сочетаний, будет счастливым, в противном случае счастливым он не будет.

На раздаче в очередь выстроились n заводчан. По очереди они будут подходить к Алевтине и называть ей гарнир, который они хотят. У Алевтины на раздаче будут все три гарнира, а также одно из горячих блюд. Заводчанину она будет выдавать гарнир, который он хочет, а также то горячее которое сейчас на раздаче. Кроме того, за всё время Алевтина готова не более чем k раз сходить в Горячий Цех и заменить горячее блюдо на раздаче на любое другое. Естественно, в начале она вольна принести на раздачу любое горячее блюдо, которое захочется.

Алевтина дружит со всеми заводчанами и уже заранее знает кому какой гарнир хочется. Всей информацией она поделилась с Вами. Алевтина добра душой и хочет, чтобы как можно больше заводчан были счастливы благодаря сочетанию гарнира и горячего. Ваша задача — сказать какое наибольшее число заводчан могут оказаться счастливыми при заданном ограничении на число замен горячего блюда на раздаче. Не подведите Алевтину!

В первой строке входных даны целые числа n и k (1⩽n⩽105, 0⩽k⩽20). В следующих n строках даны предпочтения по гарнирам в том порядке, в котором заводчане стоят в очереди, по одному на строке. Предпочтение описано одним из трёх символов: «M», «P» или «G» — макарошки, пюрешка или гречка соответственно.

Выведите какое наибольшее число заводчан будут счастливыми после обеда.

------------------------------

Примеры:
5 1
M
M
G
M
P
-> 4