Одновимірна Клікоманія
"Одновимірна Клікоманія" - це логічна комп'ютерна гра. Для неї використовується полоска розміром 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), які задають константи у формулі нарахування очокв за кожен зроблений хід.
Вихідні дані
Ціле число, рівне максимальній кількості очок, які може набрати гравець по завершенню гри.