Wesley has recently visited the arcade and has tasked himself with mastering all songs on Dance Dance Revolution. Unfortunately, the machine that Wesley has claimed is broken and is unable to keep track of his score. Can you help Wesley determine his final score?
In Dance Dance Revolution, there are 4 different moves that can be played - up, down, left, and right.
The song that Wesley plays consists of multiple beats and he will match each beat with a single move. Every move is worth point (regardless of whether it is part of a combo or not). The song is described by a sequence of characters consisting of
R, representing the moves up, down, left, and right. We will call this sequence .
A combo is defined by a specific ordering of moves played consecutively. There are different combos, which can also be described by a sequence of characters consisting of
R the of which is . Each combo is also associated with a point value , which is earned each time a combo is completed.
To determine which moves are part of combos, the following algorithm is used.
- Set the current move to the first move that Wesley performs.
- Select the longest combo such that the moves in the combo match the next moves (starting from the current move) in the sequence of moves that Wesley performs (in the same order), where is the length of the chosen combo. It may be the case that such a combo does not exist, in which case, the longest combo has a length of .
- The current move becomes the move immediately after the last move in the longest combo (or the move immediately after the current move if no such combo exists). If the current move is past the end of the sequence, terminate the algorithm.
- Go to step 2.
It can be seen that a single move may only correspond to at most one combo, although the same combo may be played multiple times.
No two combos will be identical.
Given a series of moves that Wesley performs, can you determine how many points he scored?
For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.
For all subtasks:
where is the length of .
where is the length of .
and will consist only of the characters
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
The first line will contain a string , Wesley's moves. Each character will be one of
The second line of input contains , the number of different combos.
The next lines will each contain , the combo sequence and , the points the combo is worth. Each character in will be one of
Output a single integer, the number of points that Wesley scored.
Sample Input 1
RLUDD 1 RLU 4
Sample Output 1
Sample Explanation 1
The first moves are part of the first combo, resulting in extra points, in addition to the point gained for each move, for a total of points.
Sample Input 2
UDULRL 2 ULR 3 UDU 2
Sample Output 2
Sample Explanation 2
The first moves are part of the second combo, resulting in extra points, in addition to the point gained for each move, for a total of points. Although the first combo appears in the sequence of moves, the algorithm used to assign moves to combos will not take this into consideration (even if it earns more points).
Sample Input 3
ULRURURU 3 LRURU 500 LRUR 750 URU 1000
Sample Output 3
Sample Explanation 3
The second move to the sixth move are all part of the first combo, resulting in extra points, in addition to the point gained for each move, for a total of points. Although both the second and third combos appears in the sequence of moves, the algorithm used to assign moves to combos will not take this into consideration (even if it earns more points).