C - たんごたくさん

Contest Duration: 2016-09-10(Sat) 05:00 - 2016-09-10(Sat) 07:30 (local time) (150 minutes)

C - たんごたくさん Editorial

Time Limit: 5 sec / Memory Limit: 512 MB

配点 : $700$ 点

文字列 $S$ と、要素数 $M$ の単語の集合 $P=\{P_1,\ P_2,\ …,\ P_M\}$ が与えられます。単語 $P_i$ は、整数の重み $W_i$ を持っています。

文字列 $S$ から、 $P$ に含まれる単語を重なり合わないように取り出すことを考えます。単語の重みの総和が最大値をとるように取り出すとき、その最大値はいくつでしょうか？

なお、同じ単語を複数回取り出した場合、それらの単語は別々に数えることとします。

入力は以下の形式で標準入力から与えられる。

 $S$ 
 $M$ 
 $P_1$ 
:
 $P_M$ 
 $W_1$ 
:
 $W_M$

単語の重みの総和の最大値を $1$ 行に出力せよ。

Copy

abcabcabc
3
ab
bc
ca
1
1
1

Copy

Copy

abracadabra
4
b
abra
cad
rac
1
10
50
100

Copy

Copy

abcd
2
ad
bc
1192
794

Copy