問題文

文字列 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 は英小文字からなる文字列である

入力例 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