eolymp
bolt
Try our new interface for solving problems
Problems

Одномерная Кликомания

Одномерная Кликомания

Time limit 1 second
Memory limit 64 MiB

"Одномерная Кликомания" - это логическая компьютерная игра. Для нее используется полоска размеров 1xN, разбитая на N квадратов 1x1. Каждый из квадратов окрашен в красный или желтый цвет.

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

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

В начале игры количество баллов у игрока равно нулю. После каждого его хода количество баллов пересчитывается. Если игрок очередным ходом удалил группу из L квадратов, то вычисляется число X = A·L + B, где A и B - некоторые целочисленные константы. Если число X неотрицательное, то количество баллов игрока увеличивается на X, иначе оно уменьшается на -X.

Цель игрока - набрать по окочанию игры как можно больше баллов. Напишите программу, оптимально играющую в "Одномерную Кликоманию". Программа должна получать на входе цвета всех квадратов исходной полоски, а также целые числа A и B, и возвращать максимальное количество баллов, которое может набрать игрок по окончанию игры.

Input data

В первой строке задана строка, состоящая из символов 'R'/'Y', перечисляющих слева направо цвета всех квадратов исходной полоски. Символ 'R' соответствует квадрату красного цвета, а символ 'Y' - квадрату желтого цвета.

Во второй и третьей строках соответственно целые числа A (1A1000) и B (-100B100), задающие константы в формуле начисления очков за каждый сделанный ход.

Output data

Целое число, равное максимальному количеству очков, которое может набрать игрок по окончанию игры.

Examples

Input example #1
YYYYYYY
73
14
Output example #1
525