시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB4115952.941%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

RRRGGRRRRG

예제 출력 1

34

예제 입력 2

RB

예제 출력 2

0

힌트

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