Задача D. Пузырьки 1D ≡

Условие

Сережа — большой любитель игр на сотовом телефоне. Недавно он скачал из интернета новую игру "Пузырьки 1D". Опишем правила игры.

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

За один ход разрешается выбрать любую группу, состоящую хотя бы из двух пузырьков, и взорвать ее. За взрыв группы, содержащей k пузырьков, игрок получает k² очков. После взрыва группы пузырьки, которые находились сверху, опускаются вниз.

Например, ниже на рисунке показана позиция, содержащая 10 пузырьков. В ней четыре группы, содержащие 3, 2, 4 и 1 пузырек, соответственно. Если взорвать группу, содержащую четыре пузырь- ка, то игрок получит 16 очков, и верхние 5 пузырьков опустятся вниз. В получившейся позиции 6 пузырьков, и две группы по 3 пузырька в каждой.

По заданной начальной позиции в игре выясните, сможет ли Сережа уничтожить все пузырьки, и если да, то какое максимальное количество очков он сможет заработать.

Формат входного файла

Входной файл содержит одну строку, состоящую из букв "R", "G", "B" и "Y", описывающую начальную позицию. Буквы задают цвета пузырьков в порядке просмотра сверху вниз ("R" означает красный пузырек, "G" — зеленый, "B" — синий, а "Y" — желтый).

Формат выходного файла

Выведите в выходной файл одно число — максимальное количество очков, которое сможет заработать Сережа. Если уничтожить все пузырьки невозможно, выведите 0.

В первом примере следует действовать следующим образом: сначала надо взорвать группу из четырех красных пузырьков, получив 16 очков. Затем надо взорвать в любом порядке получившиеся две группы по 3 пузырька, получив по 9 очков за каждую.

Ограничения

В заданной позиции не менее двух и не более 100 пузырьков.

Примеры тестов

RRRGGRRRRG

34

RB

0