配点 : 700 点
問題文
文字列 S 和元素数量 M 一组单词 给出了 P=\{P_1,\ P_2,\ …,\ P_M\} 。词 P_i 是整数权重 W_i 。 来自
文字列 S , 让我们考虑提取P 中包含的单词,以便它们不重叠。当我们提取单词使得它们的权重之和取最大值时,最大值是多少?
如果同一单词被多次提取,这些单词将被单独计数。
制約
- 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 是一串小写字母
入力
输入是按以下格式从标准输入给出的。
S M P_1 : P_M W_1 : W_M
出力
词权重之和的最大值为 1 行输出。 由于字符串以
入力例 1
abcabcabc 3 ab bc ca 1 1 1
出力例 1
4
入力例 2
abracadabra 4 b abra cad rac 1 10 50 100
出力例 2
111
入力例 3
abcd 2 ad bc 1192 794
出力例 3
794