Московские, осень' 14: Командный тур 2 ноября 2014

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

К счастью, скоро настало время выпускных экзаменов, игра была позабыта, а вскоре потерялась при обновлении системы. Освободившееся время Витя потратил с пользой: сдал экзамены на «хорошо» и «отлично», поступил в университет, а через шесть лет, успешно защитив магистерскую диссертацию, устроился на работу ведущим программистом.

Беда пришла, откуда не ждали. Недавно вышла новая версия игры, Zuma 2.0 . В этой версии сюжет игры сделался более разнообразным, в частности, на разных уровнях игры действуют разные правила. Игра снова захватила Витю... простите, теперь уже Виктора Сергеевича. Однако, Виктор Сергеевич осознает, что игру нужно пройти как можно быстрее, чтобы вернуться к своим должностным обязанностям. В частности, ему никак не дается предпоследний уровень, поэтому он просит Вас помочь ему сделать это.

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

• Уничтожить любые два шара, на которых написаны одинаковые буквы.
• Уничтожить любые три шара, на которых написаны гласные буквы, а именно, «A», «E», «I», «O», «U», «Y» (см. примечание).

После выстрела оставшиеся шары смыкаются, вновь образуя окружность.

Если на уровне осталось менее пяти шаров, то игрок получает очки — чем меньше шаров осталось, тем больше очков он получает. Если же осталось пять или более шаров, а выстрел сделать не получается, то уровень считается непройденным.

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