Candy Chain

Time limit7sMemory limit512 MB

Summary

Given a candy string and a list of paid parts (each reversible), find the maximum total value obtainable by repeatedly removing sold parts and rejoining the remainder.

Level: Medium5 of 10
Topics: Dynamic programming, Intervals, Brute force, String matching
Solved: No attempts yet

Problem

A candy chain is a row of single candies. Candies come in 26 flavors, and each flavor is written as a lowercase letter from a to z. Margot keeps a very fancy candy chain on display in her shop.

After school, children come to the shop and buy parts of the candy chain. Every child wants something different. For example, one child likes a part with flavors ababi and pays 3 euros for it. Another child likes a part with flavors axsa and pays 5 euros.

Margot takes one part out of the candy chain and sells it to a child. Once she takes a part out, she joins the remaining left piece and right piece, and then she either sells another part or stops.

The same sequence of flavors can be sold to the same child several times, as long as Margot can take it out of the candy chain that many times. Margot never throws away candies she cannot sell, so every part she takes out has to be sold to some child. A part can be reversed when it is sold, so axsa and asxa are the same part. Margot does not have to serve every child, and the order of the sales is free.

Compute the largest amount Margot can earn from her candy chain.

Input

The first line holds Margot's candy chain as a non-empty string.
The second line holds the number of children, an integer $C$ .
Each of the next $C$ lines holds the part one child wants and the amount that child pays, separated by one space. The wanted part is a non-empty string and the amount is an integer $P_i$ .

Limits

Margot's candy chain and every child's wanted part hold at most 50 candies.
$1 \le C \le 200$
$0 \le P_i \le 1000000$ for every $i$ with $1 \le i \le C$
Every string consists of lowercase letters a to z only.

Output

A single integer, the largest amount Margot can earn.

Examples2

Example 1

Input

acmicpcxxxacmzacmzacmzmca
5
icpc 5
cpci 1
acm 2
acmacm 10
xxx 0

Expected output

Example 2
Input
```
axsa
2
asxa 5
x 1
```
Expected output
```
5
```