BD Shelf

Time Limit : 5 sec, Memory Limit : 65536 KB
Japanese version is here

Problem J: BD Shelf

Remember the boy called Jack. He likes anime, especially programs broadcasting in midnight or early morning. In his room, there is a big shelf and it is kept organized well. And there are anime BD/DVDs which he watched or gave up because of overlapping of broadcasting time with other animes. His money is tight, but he succeeded to get W hundreds dollars because of an unexpected event. And he came up with enhancing the content of his BD shelf.

He is troubled about the usage of the unexpected income. He has a good judge for anime to choose the anime he can enjoy because he is a great anime lover. Therefore, first of all, he listed up expectable animes and assigned each anime a value that represents "a magnitude of expectation". Moreover Jack tagged a mysterious string M for each anime. However Jack did not tell you the meaning of the string M.

Your task is to write a program that reads a string X and that maximizes the sum of magnitudes of expectation when Jack bought BD/DVD boxes of anime with the budget of W hundreds dollars. Here, Jack must buy anime's BD/DVD box that have a string X as a sub-string of the string M assigned the anime. If he can not buy any boxes, output -1.

A sequence of string X is given in order in the input as query. Assume two strings X1 and X2 are given as string X, and X1 is the prefix of X2. If X1 is given in the input preceding X2, you must not buy an anime which has the minimum magnitude of expectation among animes extracted by X1 in the calculation for X2. And vice versa (X1 is the prefix of X2 and if X2 is given in the input preceding X1, ...) . For example, If three strings "a", "abc" and "ab" are given in this order in the input, In the processing for string "abc", you must not extract an anime which has the minimum magnitude of expectation among animes extracted by the processing of the string "a". In the processing for string "ab", you must not extract an anime has minimum magnitude of expectation among animes extracted by the processing of the string "abc" and "a".

Input

Input consists of multiple datasets.
A dataset is given in the following format.

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

N is an integer that represents the number of anime. Following N lines contains the information of each anime.
stringi(1≤iN) is a string consists of lowercase letters that represents string M assigned i-th anime by Jack. No two characters in this string are same.
expectationi(1≤iN) is a natural number that represents a magnitude of expectation of the i-th anime.
pricei(1≤iN) is a natural number that represents a price(cost) in hundreds to buy the i-th anime. Q is an integer that represents the number of queries.
queryi(1≤iQ) is a string consists of lowercase letters. This is a string X described in the problem statement.
N=W=0 shows the end of the input.

Constraints

There are 4 test cases. This is given by the following order.
In the first testcase, 4 datasets satisfy N≤10 and Q≤10, 6 datasets satisfy N≤5000 and Q≤5000.
In the 2nd, 3rd and 4th testcase, each satisfies N≤20000 and Q≤20000.
The time limit for this problem is the limit for each testcase.
1≤N≤20000
1≤W≤20
1≤(the length of stringi(1≤iN))≤10
1≤pricei(1≤iN)≤20
1≤expectationi(1≤iN)≤7000000
1≤Q≤20000
1≤(the length of queryi(1≤iQ))≤5
It is assured that all values for expectation are different.

Output

For each query, output an integer S on a line that represents the maximum sum of magnitudes of expectation in the following format.

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

Source: University of Aizu Programming Contest , Aizu-Wakamatsu, Japan, 2011-06-05
Problem Setter:  Yohei Mori