Копито, Папір, Ножиці (Золото)

Ви, ймовірно, чули про гру «Камінь, ножиці, папір». Корови люблять грати у схожу гру, яку вони називають «Копито, папір, ножиці».

Правила гри «Копито, папір, ножиці» прості. Дві корови грають одна проти одної. Вони рахують до трьох, після чого одночасно показують жест, що позначає або копито, або аркуш паперу, або пару ножиць. Копито перемагає ножиці (оскільки копито може роздавити ножиці), ножиці перемагають папір (оскільки ножиці можуть розрізати папір), а папір перемагає копито (оскільки копито може порізатись папером). Наприклад, якщо перша корова показує «копито», а друга — «папір», то друга корова перемагає. Звісно, гра також може закінчитись нічиєю, якщо обидві корови показують однаковий жест.

Фермер Джон хоче зіграти зі своєю найкращою коровою Бессі в $n$ партій гри «Копито, папір, ножиці». Бессі, будучи експертом у цій грі, може передбачити кожен жест ФДжона до того, як він його покаже. На жаль, Бессі, будучи коровою, також дуже лінива. Тому вона схильна показувати один і той самий жест кілька разів поспіль. Більше того, за всі партії вона готова змінити жест не більше ніж $k$ разів. Наприклад, якщо k = 2, вона може показувати «копито» у перших кількох партіях, потім переключитися на «папір» на деякий час, а потім знову переключитися на «копито» в решті партій.

За заданою послідовністю жестів, які показуватиме ФДжон, визначте максимальну кількість партій, які Бессі може виграти.