A Candy Chain is a sequence of individual candies. Candies come in 26 different flavors identified by
the lowercase letters
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.,
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.
- 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~.
- Margot's Candy Chain, as well as the candy portion of every child, is formed of at most ~50~ candies;
- ~1 \le C \le 200~;
- for all ~1 \le i \le C~, ~0 \le P_i \le 1\,000\,000~;
- all strings are formed of the lowercase characters
A single integer: the maximum amount Margot can earn.
acmicpcxxxacmzacmzacmzmca 5 icpc 5 cpci 1 acm 2 acmacm 10 xxx 0