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 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≤i≤N) 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≤i≤N) is a natural number that represents a magnitude of expectation of the i-th anime.
pricei(1≤i≤N) 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≤i≤Q) 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.
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≤i≤N))≤10
1≤pricei(1≤i≤N)≤20
1≤expectationi(1≤i≤N)≤7000000
1≤Q≤20000
1≤(the length of queryi(1≤i≤Q))≤5
It is assured that all values for expectation are different.
For each query, output an integer S on a line that represents the maximum sum of magnitudes of expectation in the following format.
S
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
111 110 100 100 11 10 111 110 100 900 300 300 2200 100 1100 1500 1400 900 -1