Candy Chain
Candy Chain is a sequence of individual candies. Candies come in 26 different flavours 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 flavours ababi, and is willing to pay 3 euros for it. Another child likes portions with flavours 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 flavours 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
First line represents Margot’s Candy Chain as a non-empty string of characters. Second line consists of the number of children, an integer c (1 ≤ c ≤ 200). 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] (0 ≤ P[i] ≤ 10^6 for all 1 ≤ i ≤ c).
All strings are formed of the lowercase characters a to z only. Margot’s Candy Chain, as well as the candy portion of every child, is formed of at most 50 candies.
Output
Print a single integer: the maximum amount Margot can earn.