One-dimensional Clickomania
"One-Dimensional Clickomania" is a logic-based computer game played on a strip of size 1xN, which is divided into N squares, each measuring 1x1. Each square is colored either red or yellow.
During each turn, the player can select any square and click on it. The game then highlights the longest contiguous group of squares of the same color that includes the selected square and removes all squares in this group. Any squares to the right of the removed group will shift left to fill the gap, maintaining the continuity of the strip:
Players can remove groups of any length, even those consisting of a single square. The game continues until all squares are removed.
Initially, the player's score is zero. After each move, the score is updated. If a group of L squares is removed, the score change is calculated as X = A·L + B, where A and B are integer constants. If X is non-negative, the score increases by X; if negative, it decreases by -X.
The objective is to maximize the score by the end of the game. Write a program that plays "One-Dimensional Clickomania" optimally. The program should take as input the colors of all squares in the strip, along with the integers A and B, and output the maximum score achievable.
Input
The first line contains a string of 'R' and 'Y' characters, representing the colors of the squares from left to right. 'R' denotes a red square, and 'Y' denotes a yellow square.
The second and third lines contain the integers A (1 ≤ A ≤ 1000) and B (-100 ≤ B ≤ 100), which are the constants used in the score calculation formula.
Output
Output a single integer, representing the maximum score the player can achieve by the end of the game.