← 返回题目列表

AtCoder · tenka1_2016_final_c

C. 很多探戈

中文机器翻译题面 查看原题

配点 : 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