Одномерная Кликомания
"Одномерная Кликомания" - это логическая компьютерная игра. Для нее используется полоска размеров 1xN, разбитая на N квадратов 1x1. Каждый из квадратов окрашен в красный или желтый цвет.
За один ход игрок может выбрать любой из квадратов и щелкнуть по нему мышкой. В результате компьютер выделяет на полоске группу максимальной длины, состоящую из стоящих подряд квадратов одинакового цвета и содержащую выделенный квадрат, и удаляет все квадраты из этой группы. При этом все квадраты, находящиеся правее удаленной группы (если они существуют), сдвигаются влево так, чтобы пристыковаться к квадратам, находящимся левее удаленной группы (если они существуют) и сохранить целостность полоски:
Игрок может удалять группы квадратов любой длины, в том числе, состоящие из одного квадрата. Игра продолжается до тех пор, пока все квадраты не удалены.
В начале игры количество баллов у игрока равно нулю. После каждого его хода количество баллов пересчитывается. Если игрок очередным ходом удалил группу из L квадратов, то вычисляется число X = A·L + B, где A и B - некоторые целочисленные константы. Если число X неотрицательное, то количество баллов игрока увеличивается на X, иначе оно уменьшается на -X.
Цель игрока - набрать по окочанию игры как можно больше баллов. Напишите программу, оптимально играющую в "Одномерную Кликоманию". Программа должна получать на входе цвета всех квадратов исходной полоски, а также целые числа A и B, и возвращать максимальное количество баллов, которое может набрать игрок по окончанию игры.
Входные данные
В первой строке задана строка, состоящая из символов 'R'/'Y', перечисляющих слева направо цвета всех квадратов исходной полоски. Символ 'R' соответствует квадрату красного цвета, а символ 'Y' - квадрату желтого цвета.
Во второй и третьей строках соответственно целые числа A (1 ≤ A ≤ 1000) и B (-100 ≤ B ≤ 100), задающие константы в формуле начисления очков за каждый сделанный ход.
Выходные данные
Целое число, равное максимальному количеству очков, которое может набрать игрок по окончанию игры.