時間制限 : sec, メモリ制限 : KB
English / Japanese  

Problem J: BD Shelf

ジャックという青年を思い出して欲しい。彼はアニメの中でも特に深夜から明け方に放送される番組が好きだ。彼の部屋にはとても大きな棚があり、それはいつも丁寧に整理されている。そこには彼が今までに視聴した、あるいは同時に放映されていたがためにやむを得ず諦めたアニメのBD/DVDがある。彼は思いもしないことからW万円を入手することに成功した。そしてその棚の内容をより充実させることを考えた。もともとお金にはあまり余裕が無い青年だ。

彼はこの思い掛けない収入の使い道に悩んでいた。一体どのアニメを買ったらいいだろうか。彼は相当なアニメ好きなので、ある程度は自分が楽しめそうなアニメ・楽しめなさそうなアニメに目が利く。したがってとりあえず気になるアニメをリストアップし、「楽しめそうな度合い」を数値化して各アニメに割り振った。さらに、ジャックはそれらに謎の文字列Mを付加したのだが、残念ながらあなたはこの文字列が何を意味するのか教えてもらうことは出来なかった。

あなたの仕事はある文字列Xに対して、それがMに含まれているアニメを抽出し、予算W万円以下でアニメのBD/DVDボックスを買ったときの楽しめそうな度合いの合計を最大化することである。ただしアニメの買い方は複数あるだろうから、楽しめそうな度合いの合計の最大値を出力して欲しい。もしひとつもアニメを買えないならば、-1を出力せよ。

この文字列Xは入力において、順番に与えられる。文字列Xとして与えられるふたつの文字列X1,X2について、X1X2の接頭辞であるとする。このとき、X1X2よりも先に与えられていたら、X2の計算処理において、X1で抽出されたアニメのうちで楽しめそうな度合いがもっとも小さいものは抽出しないようにして欲しい。逆(X1X2の接頭辞であり、X2X1よりも先に与えられていたら...)も同様である。たとえば、文字列Xがa,abc,abという順序で与えられた場合、abcの処理ではaの時の処理で抽出されたアニメのうち楽しめそうな度合いが最も小さいものは抽出してはならない。abの処理ではabcの時とaの時の処理で抽出されたアニメのうち楽しめそうな度合いが最も小さいものは抽出してはならない。

Input

入力は複数のデータセットからなる。
ひとつのデータセットは以下の形式で与えられる。

N W
string1 expectation1 price1
string2 expectation2 price2
...
stringN expectationN priceN
Q
query1
query2
...
queryQ

N は整数でアニメの数を示す。以降 N 行に各アニメに関する情報が続く。
stringi(1≤iN)は半角英小文字からなる i 番目のアニメに付加された謎の文字列 M を示す。これは同じ文字を複数回含まない。
expectationi(1≤iN)は自然数で、i 番目のアニメが楽しめそうな度合いを示す。
pricei(1≤iN)は自然数で、i 番目のアニメのBD/DVDボックスを買うためにかかるお金を万円単位で示す。
Q はクエリの数を示す。
queryi(1≤iQ) は半角英小文字からなる文字列である。これは問題文中の文字列 X にあたる。
N = W = 0のとき、入力の終了を示す。

Constraints

テストケースの数は4個ある。これらは以下のような順番で与えられる。
はじめのテストケースにおいて4個のデータセットはN≤10 および Q≤10を満たし、6個のデータセットがN≤5000 および Q≤5000を満たす。
2,3,4番目のテストケースにおいて、それぞれN≤20000 および Q≤20000を満たす。
問題の時間制限は1つのテストケースに対する制限である。
1≤N≤20000
1≤W≤20
1≤(stringi(1≤iN) の長さ)≤10
1≤pricei(1≤iN)≤20
1≤expectationi(1≤iN)≤7000000
1≤Q≤20000
1≤(queryi(1≤iQ) の長さ)≤5
各アニメに割り当てられる楽しめそうな度合いは互いに異なることが保証されている。

Output

データセットのクエリひとつにつき、以下の形式でアニメを楽しめそうな度合いの合計の最大値を示す1つの整数(S)を1行に出力せよ。

S

Sample Input

3 4
abc 1 1
abc 10 1
abc 100 1
3
a
abc
ab
3 4
ab 1 1
ab 10 1
abc 100 1
3
abc
ab
a
3 4
abc 1 1
abc 10 1
abc 100 1
3
ab
ab
ab
8 20
abcdef 100 2
bcdef 200 1
cfghj 300 3
ksjirto 400 6
ksitoew 500 2
qwertyl 600 2
kjhbvc 700 2
edfghucb 800 1
10
ks
cd
hj
e
a
g
h
j
i
a
0 0

Output for the Sample Input

111
110
100
100
11
10
111
110
100
900
300
300
2200
100
1100
1500
1400
900
-1