Можете подсказать по задаче или дать алгоритм задачи, код опять же не нужен

В столовой одного известного Завода вот-вот начнётся обед. На обеде есть три гарнира — макарошки, пюрешка и греча. К гарнирам, конечно же, полагается горячее. Горячих блюд тоже три (ну и совпадение!) — сосиски, котлетки и кура. На раздаче сегодня стоит добрая повариха Алевтина Мстиславовна. Она немного ленива, но очень любит заводчан, вот перед ней и встала задача. Итак, для начала поведаем вам прописные истины: макарошки лучше сочетать с сосисками, пюрешку с котлетками, а гречу с курой. Человек, у которого на обед одно из этих трёх сочетаний, будет счастливым, в противном случае счастливым он не будет. На раздаче в очередь выстроились n заводчан. По очереди они будут подходить к Алевтине и называть ей гарнир, который они хотят. У Алевтины на раздаче будут все три гарнира, а также одно из горячих блюд. Заводчанину она будет выдавать гарнир, который он хочет, а также то горячее которое сейчас на раздаче. Кроме того, за всё время Алевтина готова не более чем k раз сходить в Горячий Цех и заменить горячее блюдо на раздаче на любое другое. Естественно, в начале она вольна принести на раздачу любое горячее блюдо, которое захочется. Алевтина дружит со всеми заводчанами и уже заранее знает кому какой гарнир хочется. Всей информацией она поделилась с Вами. Алевтина добра душой и хочет, чтобы как можно больше заводчан были счастливы благодаря сочетанию гарнира и горячего. Ваша задача — сказать какое наибольшее число заводчан могут оказаться счастливыми при заданном ограничении на число замен горячего блюда на раздаче. Не подведите Алевтину! Формат входных данных В первой строке входных даны целые числа n и k ( 1 ⩽ n ⩽ 10 5 , 0 ⩽ k ⩽ 20 ). В следующих n строках даны предпочтения по гарнирам в том порядке, в котором заводчане стоят в очереди, по одному на строке. Предпочтение описано одним из трёх символов: «M», «P» или «G» — макарошки, пюрешка или гречка соответственно.
Формат выходных данных
Выведите какое наибольшее число заводчан будут счастливыми после обеда.
Примеры
Входные данные
5 1
M
M
G
M
P
Выходные данные
4
Примечания
Запасы гарниров и горячих блюд на раздаче считайте неограниченными.

Разберём пример. В примере последовательность желаемых гарниров такая: макарошки, макарошки, греча, макарошки, пюре; Алевтина 1 раз может поменять горячее на раздаче. Возможный вариант того, как ей поступить, следующий: сначала принести сосиски, раздать их 4-ём людям (соответственно первый, второй и четвёртый человек будут счастливы), а затем заменить горячее на котлетки (и тогда пятый человек тоже будет счастлив). Таким образом Алевтина осчастливит 4 заводчан.

 Гарнир Начало Длина Эффект

  M       0     2   -2 + 1 = -1 - это если сразу поставить гречку

  G       2     1   -1 + 1 = 0 - потеряем желающего гречки, но приобретём следующего за ним

  M       3     1   -1 + 0 = -1 - оставление гречки не осчастливит желающего пюре

  P       3     1   -1 + 0 = -1 - последний клиент 

 MMGPMMMG

k = 1 

 Гарнир Начало Длина Эффект

  M      0      2     -1

  G      2      1     -1

  P      3      1     -1

  M      4      3     -3

  G      7      1     -1