UVA13285 Candy Chain

糖果链是一连串独特的糖果。由小写字母 $a$ 到 $z$ 来表示 26 种不同的口味。Margot 的店里陈列着一条特别别致的糖果链。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=878&page=show_problem&problem=5209 [PDF](https://uva.onlinejudge.org/external/132/p13285.pdf)  放学后孩子们找她买一些糖果链。每个孩子都有不同的偏好。 例如，有一个孩子喜欢 `ababi` 味的糖，愿意花 $3$ 欧元买。 另一个孩子喜欢 `axsa` 味的糖，愿意花 $5$ 欧元买。 Margot 可以取出糖果链的一部分卖给孩子们，将剩下的部分合并在一起。之后可以继续出售糖果，也可以停止出售。 同一种口味可以多次出售给同一个孩子（只要 Margot 是能够糖果链中取出符合的）。 Margot 不会扔掉卖不出去的糖果。在出售时可将糖果的一部分翻转（例如，`axsa` 和 `asxa` 相同）。 Margot 不须为所有孩子出售糖果，也不须特别地为某个孩子出售糖果。 你的任务是帮助 Margot 计算她出售糖果链可获得的最大金额。

 第一行输入一个非空字符串表示 Margot 的糖果链。 第二行输入一个整数 $C$ 表示孩子的数量。 接下来 $C$ 行，每行输入一个非空字符串与一个整数 $P_i$，表示的 $i$ 个孩子喜欢的口味和愿意支付的金额。

 输出共一行，一个整数表示 Margot 可赚取的最大金额。

Margot 的糖果链以及孩子们喜爱的口味最多由 $50$ 颗糖果组成，$1 \le C \le 200$。 对于所有数据 $1 \le i \le C$，$0 \le P_i \le 1000000$，每个字符串仅有小写字母 $a$ 到 $z$ 组成。 由 yummy 从[讨论区](https://www.luogu.com.cn/discuss/799705)搬运。