AT_tenka1_2016_final_c たんごたくさん

给定一个字符串 $S$，以及一个包含 $M$ 个单词的集合 $P=\{P_1, P_2, \ldots, P_M\}$。每个单词 $P_i$ 都有一个整数权重 $W_i$。 现在你需要从字符串 $S$ 中取出若干属于集合 $P$ 的单词，要求这些单词在 $S$ 中不能重叠。请问，在取出的单词权重总和最大的情况下，这个最大值是多少？ 注意，如果同一个单词被取出多次，每次都要分别计数。

输入通过标准输入给出，格式如下： > $S$ $M$ $P_1$ : $P_M$ $W_1$ : $W_M$

请输出单词权重总和的最大值，输出一行。

## 限制条件 - $1 \leq |S| \leq 200000$ - $1 \leq M \leq 5000$ - $1 \leq |P_i| \leq 200$ - $1 \leq W_i \leq 10000$ - $S$ 和 $P_i$ 均为仅由小写英文字母组成的字符串。 由 ChatGPT 4.1 翻译