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 $1$ point (regardless of whether it is part of a combo or not). The song is described by a sequence of characters consisting of U, D, L, and R, representing the moves up, down, left, and right. We will call this sequence $S$.

A combo is defined by a specific ordering of moves played consecutively. There are $M$ different combos, which can also be described by a sequence of characters consisting of U, D, L, and R the $i^{th}$ of which is $C_i$. Each combo is also associated with a point value $P_i$, which is earned each time a combo is completed.

To determine which moves are part of combos, the following algorithm is used.

1. Set the current move to the first move that Wesley performs.
2. Select the longest combo such that the $|C_i|$ moves in the combo match the next $|C_i|$ moves (starting from the current move) in the sequence of moves that Wesley performs (in the same order), where $|C_i|$ 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 $0$.
3. 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.
4. 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?

Constraints

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:

$1\le |S|\le 1000$ where $|S|$ is the length of $S$.
$1\le M\le 5$
$2\le |C_i|\le 5$ where $|C_i|$ is the length of $C_i$.
$2\le P_i\le 1000$

$S$ and $C_i$ will consist only of the characters U, D, L, and R.

Subtask 1 [30%]

$M=1$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain a string $S$, Wesley's moves. Each character will be one of U, D, L, or R.

The second line of input will contain $M$, the number of different combos.

The next $M$ lines will each contain $C_i$, the combo sequence and $P_i$, the points the combo is worth. Each character in $C_i$ will be one of U, D, L, or R.

Output Specification

Output a single integer, the number of points that Wesley scored.

Sample Input 1

RLUDD
1
RLU 4

Sample Output 1

9

Sample Explanation 1

The first $3$ moves are part of the first combo, resulting in $4$ extra points, in addition to the point gained for each move, for a total of $9$ points.

Sample Input 2

UDULRL
2
ULR 3
UDU 2

Sample Output 2

8

Sample Explanation 2

The first $3$ moves are part of the second combo, resulting in $2$ extra points, in addition to the point gained for each move, for a total of $8$ 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

508

Sample Explanation 3

The second move to the sixth move are all part of the first combo, resulting in $500$ extra points, in addition to the point gained for each move, for a total of $508$ points. Although both the second and third combos appear 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).