Problem D
Candy Chain

A Candy Chain is a sequence of individual candies. Candies come in $26$ different flavors identified by the lowercase letters a to z. Margot has a particularly fancy Candy Chain displayed in her shop.

After school, children will come to her and buy portions of the Candy Chain. Every child has different preferences. For example there is a child who likes portions with flavors ababi, and is willing to pay $3$ euros for it. Another child likes portions with flavors axsa and is willing to pay $5$ euros for it.

Margot can extract portions of the Candy Chain and sell them to the children. When she extracts a portion, she joins the remaining left and right parts of the Candy Chain, and can then continue serving additional portions, or decide to stop.

The same sequence of flavors can be sold multiple times to the same child (as long as Margot is able to extract multiple instances of it from her Candy Chain). Margot never throws away candies if she cannot sell them. She can reverse candy portions while selling them (e.g., axsa and asxa are equivalent). Margot does not have to serve all children, and she does not have to serve the children in any particular order.

Your task is to help Margot compute the maximum amount she can earn from her Candy Chain.

Input

• Line $1$ represents Margot’s Candy Chain as a non-empty string of characters.

• Line $2$ consists of the number of children, an integer $C$.

• The $C$ following lines represent the preferences of each child as two items separated by a space: his or her preferred candy portion, represented by a non-empty string of characters; and what he or she is willing to pay, represented by an integer $P_ i$.

Limits

• Margot’s Candy Chain, as well as the candy portion of every child, is formed of at most $50$ candies;

• $1 \leqslant C \leqslant 200$;

• for all $1\leq i\leq C$, $0 \leqslant P_ i \leqslant 1\, 000\, 000$;

• all strings are formed of the lowercase characters a to z only.

Output

A single integer: the maximum amount Margot can earn.

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

21