Шахтарі

На двох вугільних шахтах продуктивність гірників безпосередньо залежить від різноманітності їжі, яку вони споживають.

Їжа надходить на шахти у коробках трьох типів: м'ясо, риба та хліб (так, якщо ви грали у "Settlers II" десять років тому, можете відчути ностальгію). Коли на шахту надходить чергова коробка з їжею, гірники видобувають певну кількість вугілля залежно від вмісту цієї коробки та двох попередніх коробок (або меншої кількості, якщо ще не отримували стільки), за наступними правилами:

• Якщо всі три (або менше) коробки одного типу, видобувається одна одиниця вугілля;

• Якщо серед цих трьох (або менше) коробок зустрічаються два типи їжі, видобувається дві одиниці вугілля;

• Якщо серед цих трьох коробок є всі три типи їжі, видобувається три одиниці вугілля.

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

Коробки не можна відкладати чи ділити: коробку потрібно негайно відправити або на першу, або на другу шахту. Кількість коробок, надісланих на кожну шахту, може бути довільною — навіть усі коробки можна відправити на одну шахту, якщо це вигідніше. (До речі, якщо ви у майбутньому станете чиновником, не варто так чинити!)