MOG Training #6Ended |
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.
Limits
A single integer: the maximum amount Margot can earn.