P15221 [SWERC 2017] Candy Chain

糖果链是由单个糖果组成的序列。糖果有 26 种不同的口味，用小写字母 $a$ 到 $z$ 表示。Margot 在她的店里展示了一条特别精美的糖果链。 放学后，孩子们会来到她这里购买糖果链的一部分。每个孩子有不同的偏好。例如，有一个孩子喜欢口味序列为 $ababi$ 的部分，并愿意为此支付 3 欧元。另一个孩子喜欢口味序列为 $axsa$ 的部分，并愿意支付 5 欧元。 Margot 可以从糖果链中截取部分糖果卖给孩子们。当她截取一部分后，她会将糖果链剩余的左右部分连接起来，然后可以继续为其他孩子截取更多部分，或者决定停止。 相同的口味序列可以多次卖给同一个孩子（只要 Margot 能够从她的糖果链中多次截取出该序列）。如果 Margot 无法卖出某些糖果，她绝不会丢弃它们。在出售时，她可以将糖果部分反转（例如，$axsa$ 和 $asxa$ 是等价的）。Margot 不必为所有孩子服务，也不必须以任何特定顺序服务孩子们。 你的任务是帮助 Margot 计算她能从糖果链中获得的最大收益。

- 第一行表示 Margot 的糖果链，是一个非空字符串。 - 第二行包含孩子数量，一个整数 $C$。 - 接下来的 $C$ 行表示每个孩子的偏好，每行包含两个用空格分隔的部分：他或她喜欢的糖果部分，用一个非空字符串表示；以及他或她愿意支付的金额，用一个整数 $P_i$ 表示。

一个整数：Margot 能够获得的最大收益。

#### 数据范围 - Margot 的糖果链以及每个孩子喜欢的糖果部分最多由 50 个糖果组成； - $1 \leq C \leq 200$； - 对于所有 $1 \leq i \leq C$，$0 \leq P_i \leq 1\,000\,000$； - 所有字符串仅由小写字符 $a$ 到 $z$ 组成。 翻译由 DeepSeek 完成